Lines Matching refs:node
184 static inline void mt_free_one(struct maple_node *node) in mt_free_one() argument
186 kmem_cache_free(maple_node_cache, node); in mt_free_one()
196 struct maple_node *node = container_of(head, struct maple_node, rcu); in mt_free_rcu() local
198 kmem_cache_free(maple_node_cache, node); in mt_free_rcu()
208 static void ma_free_rcu(struct maple_node *node) in ma_free_rcu() argument
210 WARN_ON(node->parent != ma_parent_ptr(node)); in ma_free_rcu()
211 call_rcu(&node->rcu, mt_free_rcu); in ma_free_rcu()
268 mas->node = MA_ERROR(err); in mas_set_err()
328 return mte_to_node(mas->node); in mas_mn()
348 static inline struct maple_enode *mt_mk_node(const struct maple_node *node, in mt_mk_node() argument
351 return (void *)((unsigned long)node | in mt_mk_node()
355 static inline void *mte_mk_root(const struct maple_enode *node) in mte_mk_root() argument
357 return (void *)((unsigned long)node | MAPLE_ROOT_NODE); in mte_mk_root()
360 static inline void *mte_safe_root(const struct maple_enode *node) in mte_safe_root() argument
362 return (void *)((unsigned long)node & ~MAPLE_ROOT_NODE); in mte_safe_root()
365 static inline void __maybe_unused *mte_set_full(const struct maple_enode *node) in mte_set_full() argument
367 return (void *)((unsigned long)node & ~MAPLE_ENODE_NULL); in mte_set_full()
370 static inline void __maybe_unused *mte_clear_full(const struct maple_enode *node) in mte_clear_full() argument
372 return (void *)((unsigned long)node | MAPLE_ENODE_NULL); in mte_clear_full()
375 static inline bool __maybe_unused mte_has_null(const struct maple_enode *node) in mte_has_null() argument
377 return (unsigned long)node & MAPLE_ENODE_NULL; in mte_has_null()
380 static __always_inline bool ma_is_root(struct maple_node *node) in ma_is_root() argument
382 return ((unsigned long)node->parent & MA_ROOT_PARENT); in ma_is_root()
385 static __always_inline bool mte_is_root(const struct maple_enode *node) in mte_is_root() argument
387 return ma_is_root(mte_to_node(node)); in mte_is_root()
569 static __always_inline bool ma_dead_node(const struct maple_node *node) in ma_dead_node() argument
575 parent = (void *)((unsigned long) node->parent & ~MAPLE_NODE_MASK); in ma_dead_node()
576 return (parent == node); in ma_dead_node()
587 struct maple_node *node; in mte_dead_node() local
589 node = mte_to_node(enode); in mte_dead_node()
590 return ma_dead_node(node); in mte_dead_node()
663 static inline unsigned long *ma_pivots(struct maple_node *node, in ma_pivots() argument
668 return node->ma64.pivot; in ma_pivots()
671 return node->mr64.pivot; in ma_pivots()
685 static inline unsigned long *ma_gaps(struct maple_node *node, in ma_gaps() argument
690 return node->ma64.gap; in ma_gaps()
745 struct maple_node *node = mte_to_node(mn); in mte_set_pivot() local
752 node->mr64.pivot[piv] = val; in mte_set_pivot()
755 node->ma64.pivot[piv] = val; in mte_set_pivot()
998 struct maple_node *node; in mas_mat_destroy() local
1003 node = mte_to_node(mat->head); in mas_mat_destroy()
1006 call_rcu(&node->rcu, mt_free_walk); in mas_mat_destroy()
1020 struct maple_node *node; in mas_descend() local
1023 node = mas_mn(mas); in mas_descend()
1024 type = mte_node_type(mas->node); in mas_descend()
1025 pivots = ma_pivots(node, type); in mas_descend()
1026 slots = ma_slots(node, type); in mas_descend()
1031 mas->node = mas_slot(mas, slots, mas->offset); in mas_descend()
1079 p_node = mte_parent(mas->node); in mas_ascend()
1083 a_type = mas_parent_type(mas, mas->node); in mas_ascend()
1084 mas->offset = mte_parent_slot(mas->node); in mas_ascend()
1088 if (p_node != mte_parent(mas->node)) in mas_ascend()
1091 mas->node = a_enode; in mas_ascend()
1151 struct maple_alloc *ret, *node = mas->alloc; in mas_pop_node() local
1162 ret = node; in mas_pop_node()
1166 if (node->node_count == 1) { in mas_pop_node()
1168 mas->alloc = node->slot[0]; in mas_pop_node()
1169 mas->alloc->total = node->total - 1; in mas_pop_node()
1170 ret = node; in mas_pop_node()
1173 node->total--; in mas_pop_node()
1174 ret = node->slot[--node->node_count]; in mas_pop_node()
1175 node->slot[node->node_count] = NULL; in mas_pop_node()
1231 struct maple_alloc *node; in mas_alloc_nodes() local
1249 node = (struct maple_alloc *)mt_alloc_one(gfp); in mas_alloc_nodes()
1250 if (!node) in mas_alloc_nodes()
1254 node->slot[0] = mas->alloc; in mas_alloc_nodes()
1255 node->node_count = 1; in mas_alloc_nodes()
1257 node->node_count = 0; in mas_alloc_nodes()
1260 mas->alloc = node; in mas_alloc_nodes()
1261 node->total = ++allocated; in mas_alloc_nodes()
1262 node->request_count = 0; in mas_alloc_nodes()
1266 node = mas->alloc; in mas_alloc_nodes()
1268 max_req = MAPLE_ALLOC_SLOTS - node->node_count; in mas_alloc_nodes()
1269 slots = (void **)&node->slot[node->node_count]; in mas_alloc_nodes()
1275 if (node->node_count == 0) { in mas_alloc_nodes()
1276 node->slot[0]->node_count = 0; in mas_alloc_nodes()
1277 node->slot[0]->request_count = 0; in mas_alloc_nodes()
1280 node->node_count += count; in mas_alloc_nodes()
1284 node = node->slot[0]; in mas_alloc_nodes()
1285 } while (unlikely(node->node_count == MAPLE_ALLOC_SLOTS)); in mas_alloc_nodes()
1376 mas->node = mte_safe_root(root); in mas_start()
1378 if (mte_dead_node(mas->node)) in mas_start()
1384 mas->node = NULL; in mas_start()
1416 static __always_inline unsigned char ma_data_end(struct maple_node *node, in ma_data_end() argument
1425 return ma_meta_end(node, type); in ma_data_end()
1429 return ma_meta_end(node, type); in ma_data_end()
1449 struct maple_node *node; in mas_data_end() local
1453 type = mte_node_type(mas->node); in mas_data_end()
1454 node = mas_mn(mas); in mas_data_end()
1456 return ma_meta_end(node, type); in mas_data_end()
1458 pivots = ma_pivots(node, type); in mas_data_end()
1459 if (unlikely(ma_dead_node(node))) in mas_data_end()
1464 return ma_meta_end(node, type); in mas_data_end()
1488 mt = mte_node_type(mas->node); in mas_leaf_max_gap()
1563 ma_max_gap(struct maple_node *node, unsigned long *gaps, enum maple_type mt, in ma_max_gap() argument
1569 i = offset = ma_meta_end(node, mt); in ma_max_gap()
1592 struct maple_node *node; in mas_max_gap() local
1594 mt = mte_node_type(mas->node); in mas_max_gap()
1598 node = mas_mn(mas); in mas_max_gap()
1600 offset = ma_meta_gap(node); in mas_max_gap()
1601 gaps = ma_gaps(node, mt); in mas_max_gap()
1624 pnode = mte_parent(mas->node); in mas_parent_gap()
1625 pmt = mas_parent_type(mas, mas->node); in mas_parent_gap()
1674 if (mte_is_root(mas->node)) in mas_update_gap()
1679 pslot = mte_parent_slot(mas->node); in mas_update_gap()
1680 p_gap = ma_gaps(mte_parent(mas->node), in mas_update_gap()
1681 mas_parent_type(mas, mas->node))[pslot]; in mas_update_gap()
1697 struct maple_node *node = mte_to_node(parent); in mas_adopt_children() local
1698 void __rcu **slots = ma_slots(node, type); in mas_adopt_children()
1699 unsigned long *pivots = ma_pivots(node, type); in mas_adopt_children()
1703 offset = ma_data_end(node, type, pivots, mas->max); in mas_adopt_children()
1723 if (mte_is_root(mas->node)) { in mas_put_in_tree()
1725 rcu_assign_pointer(mas->tree->ma_root, mte_mk_root(mas->node)); in mas_put_in_tree()
1729 offset = mte_parent_slot(mas->node); in mas_put_in_tree()
1730 slots = ma_slots(mte_parent(mas->node), in mas_put_in_tree()
1731 mas_parent_type(mas, mas->node)); in mas_put_in_tree()
1732 rcu_assign_pointer(slots[offset], mas->node); in mas_put_in_tree()
1766 struct maple_node *node; in mas_find_child() local
1769 mt = mte_node_type(mas->node); in mas_find_child()
1770 node = mas_mn(mas); in mas_find_child()
1771 slots = ma_slots(node, mt); in mas_find_child()
1772 pivots = ma_pivots(node, mt); in mas_find_child()
1773 end = ma_data_end(node, mt, pivots, mas->max); in mas_find_child()
1776 if (mte_parent(entry) == node) { in mas_find_child()
1925 struct maple_node *node; in mas_mab_cp() local
1931 node = mas_mn(mas); in mas_mab_cp()
1932 mt = mte_node_type(mas->node); in mas_mab_cp()
1933 pivots = ma_pivots(node, mt); in mas_mab_cp()
1956 slots = ma_slots(node, mt); in mas_mab_cp()
1959 gaps = ma_gaps(node, mt); in mas_mab_cp()
1971 static inline void mas_leaf_set_meta(struct maple_node *node, in mas_leaf_set_meta() argument
1975 ma_set_meta(node, mt, 0, end); in mas_leaf_set_meta()
1990 enum maple_type mt = mte_node_type(mas->node); in mab_mas_cp()
1991 struct maple_node *node = mte_to_node(mas->node); in mab_mas_cp() local
1992 void __rcu **slots = ma_slots(node, mt); in mab_mas_cp()
1993 unsigned long *pivots = ma_pivots(node, mt); in mab_mas_cp()
2019 gaps = ma_gaps(node, mt); in mab_mas_cp()
2028 ma_set_meta(node, mt, offset, end); in mab_mas_cp()
2030 mas_leaf_set_meta(node, mt, end); in mab_mas_cp()
2046 if (mte_is_root(mas->node)) in mas_bulk_rebalance()
2138 unsigned int p_slot = mte_parent_slot(mas->node); in mas_prev_sibling()
2160 if (mte_is_root(mas->node)) in mas_next_sibling()
2165 parent.offset = mte_parent_slot(mas->node) + 1; in mas_next_sibling()
2185 mas->node = enode; in mas_node_or_none()
2188 mas->node = NULL; in mas_node_or_none()
2212 wr_mas->node = mas_mn(wr_mas->mas); in mas_wr_node_walk()
2213 wr_mas->pivots = ma_pivots(wr_mas->node, wr_mas->type); in mas_wr_node_walk()
2214 count = mas->end = ma_data_end(wr_mas->node, wr_mas->type, in mas_wr_node_walk()
2234 mas_mab_cp(mast->orig_r, 0, mt_slot_count(mast->orig_r->node), in mast_rebalance_next()
2296 } while (!mte_is_root(mast->orig_r->node)); in mast_spanning_rebalance()
2322 wr_mas.type = mte_node_type(mast->orig_r->node); in mast_ascend()
2328 wr_mas.type = mte_node_type(mast->orig_l->node); in mast_ascend()
2428 mas_set_parent(mas, mas->node, left, *slot); in mas_set_split_parent()
2430 mas_set_parent(mas, mas->node, right, (*slot) - split - 1); in mas_set_split_parent()
2515 enode = tmp_mas->node; in mas_topiary_node()
2557 while (!mte_is_leaf(tmp[0].node)) { in mas_topiary_replace()
2569 mas_adopt_children(&tmp[i], tmp[i].node); in mas_topiary_replace()
2588 tmp[0].node = old_enode; in mas_topiary_replace()
2604 mat_add(&subtrees, tmp_next[n].node); in mas_topiary_replace()
2622 } while (!mte_is_leaf(tmp[0].node)); in mas_topiary_replace()
2643 if (mte_is_leaf(mas->node)) in mas_wmb_replace()
2715 mt_slot_count(mast->orig_r->node), mast->bn, in mast_combine_cp_right()
2727 if (mast->bn->b_end > mt_min_slot_count(mast->orig_l->node)) in mast_sufficient()
2740 if (mast->bn->b_end >= mt_slot_count(mast->orig_l->node)) in mast_overflow()
2750 struct maple_node *node; in mtree_range_walk() local
2758 next = mas->node; in mtree_range_walk()
2763 node = mte_to_node(next); in mtree_range_walk()
2765 pivots = ma_pivots(node, type); in mtree_range_walk()
2766 end = ma_data_end(node, type, pivots, max); in mtree_range_walk()
2786 slots = ma_slots(node, type); in mtree_range_walk()
2788 if (unlikely(ma_dead_node(node))) in mtree_range_walk()
2798 mas->node = last; in mtree_range_walk()
2863 mast->bn->type = mte_node_type(mast->orig_l->node); in mas_spanning_rebalance()
2910 l_mas.node = mt_mk_node(ma_mnode_ptr(mas_pop_node(mas)), in mas_spanning_rebalance()
2911 mte_node_type(mast->orig_l->node)); in mas_spanning_rebalance()
2914 mas_set_parent(mas, left, l_mas.node, slot); in mas_spanning_rebalance()
2916 mas_set_parent(mas, middle, l_mas.node, ++slot); in mas_spanning_rebalance()
2919 mas_set_parent(mas, right, l_mas.node, ++slot); in mas_spanning_rebalance()
2924 while (!mte_is_root(mast->orig_l->node)) in mas_spanning_rebalance()
2930 old_enode = mast->orig_l->node; in mas_spanning_rebalance()
2932 mas->node = l_mas.node; in mas_spanning_rebalance()
2974 mast.bn->type = mte_node_type(mas->node); in mas_rebalance()
2979 mas_mab_cp(&r_mas, 0, mt_slot_count(r_mas.node), b_node, b_end); in mas_rebalance()
3005 enum maple_type mt = mte_node_type(mas->node); in mas_destroy_rebalance()
3006 struct maple_node reuse, *newnode, *parent, *new_left, *left, *node; in mas_destroy_rebalance() local
3025 node = mas_mn(mas); in mas_destroy_rebalance()
3026 newnode->parent = node->parent; in mas_destroy_rebalance()
3039 memcpy(slots + tmp, ma_slots(node, mt), sizeof(void *) * end); in mas_destroy_rebalance()
3040 memcpy(pivs + tmp, ma_pivots(node, mt), sizeof(unsigned long) * end); in mas_destroy_rebalance()
3044 old_eparent = mt_mk_node(mte_parent(l_mas.node), in mas_destroy_rebalance()
3045 mas_parent_type(&l_mas, l_mas.node)); in mas_destroy_rebalance()
3058 memcpy(node, newnode, sizeof(struct maple_node)); in mas_destroy_rebalance()
3059 ma_set_meta(node, mt, 0, tmp - 1); in mas_destroy_rebalance()
3060 mte_set_pivot(old_eparent, mte_parent_slot(l_mas.node), in mas_destroy_rebalance()
3074 mas->node = mt_mk_node(newnode, mt); in mas_destroy_rebalance()
3079 mt = mte_node_type(l_mas.node); in mas_destroy_rebalance()
3085 l_mas.node = mt_mk_node(new_left, mt); in mas_destroy_rebalance()
3088 offset = mte_parent_slot(mas->node); in mas_destroy_rebalance()
3089 mt = mas_parent_type(&l_mas, l_mas.node); in mas_destroy_rebalance()
3094 rcu_assign_pointer(slots[offset], mas->node); in mas_destroy_rebalance()
3095 rcu_assign_pointer(slots[offset - 1], l_mas.node); in mas_destroy_rebalance()
3100 mte_set_gap(eparent, mte_parent_slot(mas->node), gap); in mas_destroy_rebalance()
3102 mte_set_gap(eparent, mte_parent_slot(l_mas.node), gap); in mas_destroy_rebalance()
3107 mas_adopt_children(mas, mas->node); in mas_destroy_rebalance()
3124 if (mte_is_root(mas->node)) { in mas_split_final_node()
3136 mas_set_parent(mas, mast->l->node, ancestor, mast->l->offset); in mas_split_final_node()
3137 mas_set_parent(mas, mast->r->node, ancestor, mast->r->offset); in mas_split_final_node()
3140 mast->l->node = ancestor; in mas_split_final_node()
3160 if (mte_is_root(mas->node)) { in mast_fill_bnode()
3164 mas->offset = mte_parent_slot(mas->node); in mast_fill_bnode()
3171 mab_set_b_end(mast->bn, mast->l, mast->l->node); in mast_fill_bnode()
3173 mab_set_b_end(mast->bn, mast->r, mast->r->node); in mast_fill_bnode()
3178 mas_mab_cp(mas, split + skip, mt_slot_count(mas->node) - 1, in mast_fill_bnode()
3182 mast->bn->type = mte_node_type(mas->node); in mast_fill_bnode()
3198 mte_set_pivot(mast->r->node, 0, mast->r->max); in mast_split_data()
3200 mast->l->offset = mte_parent_slot(mas->node); in mast_split_data()
3203 if (mte_is_leaf(mas->node)) in mast_split_data()
3207 mas_set_split_parent(mast->orig_l, mast->l->node, mast->r->node, in mast_split_data()
3209 mas_set_split_parent(mast->orig_r, mast->l->node, mast->r->node, in mast_split_data()
3242 space = 2 * mt_slot_count(mas->node) - 2; in mas_push_data()
3269 tmp_mas.node = mast->l->node; in mas_push_data()
3272 tmp_mas.node = mast->r->node; in mas_push_data()
3337 l_mas.node = mas_new_ma_node(mas, b_node); in mas_split()
3338 r_mas.node = mas_new_ma_node(mas, b_node); in mas_split()
3366 old = mas->node; in mas_split()
3367 mas->node = l_mas.node; in mas_split()
3400 struct maple_node *node; in mas_root_expand() local
3405 node = mas_pop_node(mas); in mas_root_expand()
3406 pivots = ma_pivots(node, type); in mas_root_expand()
3407 slots = ma_slots(node, type); in mas_root_expand()
3408 node->parent = ma_parent_ptr(mas_tree_parent(mas)); in mas_root_expand()
3409 mas->node = mt_mk_node(node, type); in mas_root_expand()
3429 ma_set_meta(node, maple_leaf_64, 0, slot); in mas_root_expand()
3431 rcu_assign_pointer(mas->tree->ma_root, mte_mk_root(mas->node)); in mas_root_expand()
3500 wr_mas->type = mte_node_type(wr_mas->mas->node); in mas_wr_walk_descend()
3502 wr_mas->slots = ma_slots(wr_mas->node, wr_mas->type); in mas_wr_walk_descend()
3509 wr_mas->mas->node = wr_mas->content; in mas_wr_walk_traverse()
3621 struct maple_node *node; in mtree_lookup_walk() local
3627 next = mas->node; in mtree_lookup_walk()
3629 node = mte_to_node(next); in mtree_lookup_walk()
3631 pivots = ma_pivots(node, type); in mtree_lookup_walk()
3639 slots = ma_slots(node, type); in mtree_lookup_walk()
3641 if (unlikely(ma_dead_node(node))) in mtree_lookup_walk()
3665 struct maple_node *node; in mas_new_root() local
3679 node = mas_pop_node(mas); in mas_new_root()
3680 pivots = ma_pivots(node, type); in mas_new_root()
3681 slots = ma_slots(node, type); in mas_new_root()
3682 node->parent = ma_parent_ptr(mas_tree_parent(mas)); in mas_new_root()
3683 mas->node = mt_mk_node(node, type); in mas_new_root()
3689 rcu_assign_pointer(mas->tree->ma_root, mte_mk_root(mas->node)); in mas_new_root()
3860 struct maple_enode *old_enode = mas->node; in mas_wr_node_store()
3862 mas->node = mt_mk_node(newnode, wr_mas->type); in mas_wr_node_store()
3865 memcpy(wr_mas->node, newnode, sizeof(struct maple_node)); in mas_wr_node_store()
4003 ma_set_meta(wr_mas->node, wr_mas->type, 0, new_end); in mas_wr_append()
4129 if (mte_is_leaf(mas->node) && mas->last == mas->max) in mas_wr_prealloc_setup()
4220 if (!mte_is_root(mas->node) && !(mas->mas_flags & MA_STATE_BULK)) in mas_wr_store_type()
4354 return xa_err(mas->node); in mas_alloc_cyclic()
4376 struct maple_node *node, const unsigned long index) in mas_rewalk_if_dead() argument
4378 if (unlikely(ma_dead_node(node))) { in mas_rewalk_if_dead()
4401 struct maple_node *node; in mas_prev_node() local
4405 node = mas_mn(mas); in mas_prev_node()
4415 if (ma_is_root(node)) in mas_prev_node()
4423 node = mas_mn(mas); in mas_prev_node()
4427 mt = mte_node_type(mas->node); in mas_prev_node()
4430 slots = ma_slots(node, mt); in mas_prev_node()
4431 mas->node = mas_slot(mas, slots, offset); in mas_prev_node()
4432 if (unlikely(ma_dead_node(node))) in mas_prev_node()
4435 mt = mte_node_type(mas->node); in mas_prev_node()
4436 node = mas_mn(mas); in mas_prev_node()
4437 pivots = ma_pivots(node, mt); in mas_prev_node()
4438 offset = ma_data_end(node, mt, pivots, max); in mas_prev_node()
4439 if (unlikely(ma_dead_node(node))) in mas_prev_node()
4443 slots = ma_slots(node, mt); in mas_prev_node()
4444 mas->node = mas_slot(mas, slots, offset); in mas_prev_node()
4445 pivots = ma_pivots(node, mt); in mas_prev_node()
4446 if (unlikely(ma_dead_node(node))) in mas_prev_node()
4453 if (unlikely(mte_dead_node(mas->node))) in mas_prev_node()
4460 if (unlikely(ma_dead_node(node))) in mas_prev_node()
4483 struct maple_node *node; in mas_prev_slot() local
4487 node = mas_mn(mas); in mas_prev_slot()
4488 type = mte_node_type(mas->node); in mas_prev_slot()
4489 pivots = ma_pivots(node, type); in mas_prev_slot()
4490 if (unlikely(mas_rewalk_if_dead(mas, node, save_point))) in mas_prev_slot()
4496 if (unlikely(mas_rewalk_if_dead(mas, node, save_point))) in mas_prev_slot()
4521 node = mas_mn(mas); in mas_prev_slot()
4522 type = mte_node_type(mas->node); in mas_prev_slot()
4523 pivots = ma_pivots(node, type); in mas_prev_slot()
4527 slots = ma_slots(node, type); in mas_prev_slot()
4529 if (unlikely(mas_rewalk_if_dead(mas, node, save_point))) in mas_prev_slot()
4562 static int mas_next_node(struct ma_state *mas, struct maple_node *node, in mas_next_node() argument
4580 if (ma_is_root(node)) in mas_next_node()
4588 node = mas_mn(mas); in mas_next_node()
4589 mt = mte_node_type(mas->node); in mas_next_node()
4590 pivots = ma_pivots(node, mt); in mas_next_node()
4591 node_end = ma_data_end(node, mt, pivots, mas->max); in mas_next_node()
4592 if (unlikely(ma_dead_node(node))) in mas_next_node()
4597 slots = ma_slots(node, mt); in mas_next_node()
4600 if (unlikely(ma_dead_node(node))) in mas_next_node()
4608 mas->node = enode; in mas_next_node()
4609 node = mas_mn(mas); in mas_next_node()
4610 mt = mte_node_type(mas->node); in mas_next_node()
4611 slots = ma_slots(node, mt); in mas_next_node()
4613 if (unlikely(ma_dead_node(node))) in mas_next_node()
4618 pivots = ma_pivots(node, mt); in mas_next_node()
4625 if (unlikely(ma_dead_node(node))) in mas_next_node()
4628 mas->node = enode; in mas_next_node()
4633 if (unlikely(ma_dead_node(node))) in mas_next_node()
4655 struct maple_node *node; in mas_next_slot() local
4660 node = mas_mn(mas); in mas_next_slot()
4661 type = mte_node_type(mas->node); in mas_next_slot()
4662 pivots = ma_pivots(node, type); in mas_next_slot()
4663 if (unlikely(mas_rewalk_if_dead(mas, node, save_point))) in mas_next_slot()
4672 if (unlikely(mas_rewalk_if_dead(mas, node, save_point))) in mas_next_slot()
4695 if (mas_next_node(mas, node, max)) { in mas_next_slot()
4705 node = mas_mn(mas); in mas_next_slot()
4706 type = mte_node_type(mas->node); in mas_next_slot()
4707 pivots = ma_pivots(node, type); in mas_next_slot()
4711 slots = ma_slots(node, type); in mas_next_slot()
4713 if (unlikely(mas_rewalk_if_dead(mas, node, save_point))) in mas_next_slot()
4745 enum maple_type type = mte_node_type(mas->node); in mas_rev_awalk()
4746 struct maple_node *node = mas_mn(mas); in mas_rev_awalk() local
4762 pivots = ma_pivots(node, type); in mas_rev_awalk()
4763 slots = ma_slots(node, type); in mas_rev_awalk()
4764 gaps = ma_gaps(node, type); in mas_rev_awalk()
4814 mas->node = mas_slot(mas, slots, offset); in mas_rev_awalk()
4821 if (!mte_is_root(mas->node)) in mas_rev_awalk()
4831 enum maple_type type = mte_node_type(mas->node); in mas_anode_descend()
4836 struct maple_node *node; in mas_anode_descend() local
4844 node = mas_mn(mas); in mas_anode_descend()
4845 pivots = ma_pivots(node, type); in mas_anode_descend()
4846 slots = ma_slots(node, type); in mas_anode_descend()
4847 gaps = ma_gaps(node, type); in mas_anode_descend()
4850 data_end = ma_data_end(node, type, pivots, mas->max); in mas_anode_descend()
4871 mas->node = mas_slot(mas, slots, offset); in mas_anode_descend()
4932 if (mte_is_root(mas->node)) { in mas_rewind_node()
4958 if (mte_is_root(mas->node)) { in mas_skip_node()
4992 if (last == mas->node) in mas_awalk()
4995 last = mas->node; in mas_awalk()
5046 struct maple_node *node; in mas_empty_area() local
5071 return xa_err(mas->node); in mas_empty_area()
5074 node = mas_mn(mas); in mas_empty_area()
5075 mt = mte_node_type(mas->node); in mas_empty_area()
5076 pivots = ma_pivots(node, mt); in mas_empty_area()
5081 mas->end = ma_data_end(node, mt, pivots, mas->max); in mas_empty_area()
5097 struct maple_enode *last = mas->node; in mas_empty_area_rev()
5123 if (last == mas->node) { in mas_empty_area_rev()
5127 last = mas->node; in mas_empty_area_rev()
5132 return xa_err(mas->node); in mas_empty_area_rev()
5161 struct maple_node *node; in mte_dead_leaves() local
5169 node = mte_to_node(entry); in mte_dead_leaves()
5171 if (!node || !type) in mte_dead_leaves()
5175 node->type = type; in mte_dead_leaves()
5176 rcu_assign_pointer(slots[offset], node); in mte_dead_leaves()
5191 struct maple_node *node, *next; in mte_dead_walk() local
5197 node = mte_to_node(*enode); in mte_dead_walk()
5198 slots = ma_slots(node, node->type); in mte_dead_walk()
5216 struct maple_node *node, *start; in mt_free_walk() local
5221 node = container_of(head, struct maple_node, rcu); in mt_free_walk()
5223 if (ma_is_leaf(node->type)) in mt_free_walk()
5226 start = node; in mt_free_walk()
5227 enode = mt_mk_node(node, node->type); in mt_free_walk()
5229 node = mte_to_node(enode); in mt_free_walk()
5231 mt_free_bulk(node->slot_len, slots); in mt_free_walk()
5232 offset = node->parent_slot + 1; in mt_free_walk()
5233 enode = node->piv_parent; in mt_free_walk()
5234 if (mte_to_node(enode) == node) in mt_free_walk()
5243 node = mte_to_node(enode); in mt_free_walk()
5244 } while ((node != start) || (node->slot_len < offset)); in mt_free_walk()
5246 slots = ma_slots(node, node->type); in mt_free_walk()
5247 mt_free_bulk(node->slot_len, slots); in mt_free_walk()
5250 mt_free_rcu(&node->rcu); in mt_free_walk()
5256 struct maple_node *node; in mte_destroy_descend() local
5264 node = mte_to_node(*enode); in mte_destroy_descend()
5266 slots = ma_slots(node, type); in mte_destroy_descend()
5272 node->type = type; in mte_destroy_descend()
5273 node->piv_parent = prev; in mte_destroy_descend()
5274 node->parent_slot = offset; in mte_destroy_descend()
5287 struct maple_node *node = mte_to_node(enode); in mt_destroy_walk() local
5291 node->type = mte_node_type(enode); in mt_destroy_walk()
5297 node = mte_to_node(enode); // Updated in the above call. in mt_destroy_walk()
5303 node->slot_len = mte_dead_leaves(enode, mt, slots); in mt_destroy_walk()
5305 mt_free_bulk(node->slot_len, slots); in mt_destroy_walk()
5306 offset = node->parent_slot + 1; in mt_destroy_walk()
5307 enode = node->piv_parent; in mt_destroy_walk()
5308 if (mte_to_node(enode) == node) in mt_destroy_walk()
5323 node = mte_to_node(enode); in mt_destroy_walk()
5326 node = mte_to_node(enode); in mt_destroy_walk()
5327 node->slot_len = mte_dead_leaves(enode, mt, slots); in mt_destroy_walk()
5329 mt_free_bulk(node->slot_len, slots); in mt_destroy_walk()
5333 mt_free_rcu(&node->rcu); in mt_destroy_walk()
5335 mt_clear_meta(mt, node, node->type); in mt_destroy_walk()
5348 struct maple_node *node = mte_to_node(enode); in mte_destroy_walk() local
5352 call_rcu(&node->rcu, mt_free_walk); in mte_destroy_walk()
5440 ret = xa_err(mas->node); in mas_store_gfp()
5504 ret = xa_err(mas->node); in mas_preallocate()
5525 struct maple_alloc *node; in mas_destroy() local
5541 if (end < mt_min_slot_count(mas->node) - 1) in mas_destroy()
5550 node = mas->alloc; in mas_destroy()
5551 mas->alloc = node->slot[0]; in mas_destroy()
5552 if (node->node_count > 1) { in mas_destroy()
5553 size_t count = node->node_count - 1; in mas_destroy()
5555 mt_free_bulk(count, (void __rcu **)&node->slot[1]); in mas_destroy()
5558 mt_free_one(ma_mnode_ptr(node)); in mas_destroy()
5581 struct maple_enode *enode = mas->node; in mas_expected_entries()
5620 ret = xa_err(mas->node); in mas_expected_entries()
5621 mas->node = enode; in mas_expected_entries()
5903 mas->node = NULL; in mas_pause()
6237 if (likely(mas->node != MA_ERROR(-ENOMEM))) in mas_nomem()
6380 ret = xa_err(ms.node); in mtree_insert_range()
6432 ret = xa_err(mas.node); in mtree_alloc_range()
6514 ret = xa_err(mas.node); in mtree_alloc_rrange()
6561 struct maple_node *node; in mas_dup_free() local
6570 while (!mte_is_root(mas->node)) { in mas_dup_free()
6577 } while (!mte_is_leaf(mas->node)); in mas_dup_free()
6582 node = mte_to_node(mas->node); in mas_dup_free()
6583 type = mte_node_type(mas->node); in mas_dup_free()
6584 slots = ma_slots(node, type); in mas_dup_free()
6591 node = mte_to_node(mas->node); in mas_dup_free()
6592 mt_free_one(node); in mas_dup_free()
6607 struct maple_node *node = mte_to_node(mas->node); in mas_copy_node() local
6608 struct maple_node *new_node = mte_to_node(new_mas->node); in mas_copy_node()
6612 memcpy(new_node, node, sizeof(struct maple_node)); in mas_copy_node()
6614 val = (unsigned long)node->parent & MAPLE_NODE_MASK; in mas_copy_node()
6630 struct maple_node *node = mte_to_node(mas->node); in mas_dup_alloc() local
6631 struct maple_node *new_node = mte_to_node(new_mas->node); in mas_dup_alloc()
6639 type = mte_node_type(mas->node); in mas_dup_alloc()
6650 slots = ma_slots(node, type); in mas_dup_alloc()
6674 struct maple_node *node; in mas_dup_build() local
6689 node = mt_alloc_one(gfp); in mas_dup_build()
6690 if (!node) { in mas_dup_build()
6696 type = mte_node_type(mas->node); in mas_dup_build()
6697 root = mt_mk_node(node, type); in mas_dup_build()
6698 new_mas->node = root; in mas_dup_build()
6704 if (!mte_is_leaf(mas->node)) { in mas_dup_build()
6729 parent = ma_parent_ptr(mte_to_node(new_mas->node)); in mas_dup_build()
6772 ret = xa_err(mas.node); in __mt_dup()
6812 ret = xa_err(mas.node); in mtree_dup()
7020 return mas_slot(mas, ma_slots(mas_mn(mas), mte_node_type(mas->node)), in mas_get_slot()
7028 struct maple_enode *p, *mn = mas->node; in mas_dfs_postorder()
7038 mas->node = mn; in mas_dfs_postorder()
7041 p = mas->node; in mas_dfs_postorder()
7047 mas->node = p; in mas_dfs_postorder()
7096 struct maple_range_64 *node = &mte_to_node(entry)->mr64; in mt_dump_range64() local
7105 pr_cont(PTR_FMT " %lX ", node->slot[i], node->pivot[i]); in mt_dump_range64()
7108 pr_cont(PTR_FMT " %lu ", node->slot[i], node->pivot[i]); in mt_dump_range64()
7111 pr_cont(PTR_FMT "\n", node->slot[i]); in mt_dump_range64()
7116 last = node->pivot[i]; in mt_dump_range64()
7117 else if (!node->slot[i] && max != mt_node_max(entry)) in mt_dump_range64()
7122 mt_dump_entry(mt_slot(mt, node->slot, i), in mt_dump_range64()
7124 else if (node->slot[i]) in mt_dump_range64()
7125 mt_dump_node(mt, mt_slot(mt, node->slot, i), in mt_dump_range64()
7134 node, last, max, i); in mt_dump_range64()
7138 node, last, max, i); in mt_dump_range64()
7149 struct maple_arange_64 *node = &mte_to_node(entry)->ma64; in mt_dump_arange64() local
7157 pr_cont("%lx ", node->gap[i]); in mt_dump_arange64()
7160 pr_cont("%lu ", node->gap[i]); in mt_dump_arange64()
7163 pr_cont("| %02X %02X| ", node->meta.end, node->meta.gap); in mt_dump_arange64()
7167 pr_cont(PTR_FMT " %lX ", node->slot[i], node->pivot[i]); in mt_dump_arange64()
7170 pr_cont(PTR_FMT " %lu ", node->slot[i], node->pivot[i]); in mt_dump_arange64()
7173 pr_cont(PTR_FMT "\n", node->slot[i]); in mt_dump_arange64()
7178 last = node->pivot[i]; in mt_dump_arange64()
7179 else if (!node->slot[i]) in mt_dump_arange64()
7183 if (node->slot[i]) in mt_dump_arange64()
7184 mt_dump_node(mt, mt_slot(mt, node->slot, i), in mt_dump_arange64()
7193 node, last, max, i); in mt_dump_arange64()
7197 node, last, max, i); in mt_dump_arange64()
7208 struct maple_node *node = mte_to_node(entry); in mt_dump_node() local
7214 pr_cont("node " PTR_FMT " depth %d type %d parent " PTR_FMT, node, in mt_dump_node()
7215 depth, type, node ? node->parent : NULL); in mt_dump_node()
7222 mt_dump_entry(mt_slot(mt, node->slot, i), in mt_dump_node()
7260 struct maple_enode *mte = mas->node; in mas_validate_gaps()
7261 struct maple_node *p_mn, *node = mte_to_node(mte); in mas_validate_gaps() local
7262 enum maple_type mt = mte_node_type(mas->node); in mas_validate_gaps()
7267 unsigned long *pivots = ma_pivots(node, mt); in mas_validate_gaps()
7283 gaps = ma_gaps(node, mt); in mas_validate_gaps()
7315 offset = ma_meta_gap(node); in mas_validate_gaps()
7317 pr_err("gap offset " PTR_FMT "[%u] is invalid\n", node, offset); in mas_validate_gaps()
7323 node, offset, max_gap); in mas_validate_gaps()
7330 node, i); in mas_validate_gaps()
7339 p_slot = mte_parent_slot(mas->node); in mas_validate_gaps()
7352 struct maple_enode *node; in mas_validate_parent_slot() local
7358 if (mte_is_root(mas->node)) in mas_validate_parent_slot()
7361 p_slot = mte_parent_slot(mas->node); in mas_validate_parent_slot()
7362 p_type = mas_parent_type(mas, mas->node); in mas_validate_parent_slot()
7363 parent = mte_parent(mas->node); in mas_validate_parent_slot()
7370 node = mas_slot(mas, slots, i); in mas_validate_parent_slot()
7372 if (node != mas->node) in mas_validate_parent_slot()
7375 MT_BUG_ON(mas->tree, node != mas->node); in mas_validate_parent_slot()
7376 } else if (node == mas->node) { in mas_validate_parent_slot()
7379 MT_BUG_ON(mas->tree, node == mas->node); in mas_validate_parent_slot()
7386 enum maple_type type = mte_node_type(mas->node); in mas_validate_child_slot()
7387 void __rcu **slots = ma_slots(mte_to_node(mas->node), type); in mas_validate_child_slot()
7388 unsigned long *pivots = ma_pivots(mte_to_node(mas->node), type); in mas_validate_child_slot()
7392 if (mte_is_leaf(mas->node)) in mas_validate_child_slot()
7411 if (mte_parent(child) != mte_to_node(mas->node)) { in mas_validate_child_slot()
7414 mte_to_node(mas->node)); in mas_validate_child_slot()
7432 enum maple_type type = mte_node_type(mas->node); in mas_validate_limits()
7433 void __rcu **slots = ma_slots(mte_to_node(mas->node), type); in mas_validate_limits()
7507 while (!mte_is_leaf(mas.node)) in mt_validate_nulls()
7510 slots = ma_slots(mte_to_node(mas.node), mte_node_type(mas.node)); in mt_validate_nulls()
7524 slots = ma_slots(mte_to_node(mas.node), in mt_validate_nulls()
7525 mte_node_type(mas.node)); in mt_validate_nulls()
7548 while (!mte_is_leaf(mas.node)) in mt_validate()
7552 MAS_WARN_ON(&mas, mte_dead_node(mas.node)); in mt_validate()
7554 if (MAS_WARN_ON(&mas, (end < mt_min_slot_count(mas.node)) && in mt_validate()
7555 (!mte_is_root(mas.node)))) { in mt_validate()
7574 mas->tree, mas->node); in mas_dump()
7648 wr_mas->node, wr_mas->r_min, wr_mas->r_max); in mas_wr_dump()