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()
1157 struct maple_alloc *ret, *node = mas->alloc; in mas_pop_node() local
1168 ret = node; in mas_pop_node()
1172 if (node->node_count == 1) { in mas_pop_node()
1174 mas->alloc = node->slot[0]; in mas_pop_node()
1175 mas->alloc->total = node->total - 1; in mas_pop_node()
1176 ret = node; in mas_pop_node()
1179 node->total--; in mas_pop_node()
1180 ret = node->slot[--node->node_count]; in mas_pop_node()
1181 node->slot[node->node_count] = NULL; in mas_pop_node()
1237 struct maple_alloc *node; in mas_alloc_nodes() local
1255 node = (struct maple_alloc *)mt_alloc_one(gfp); in mas_alloc_nodes()
1256 if (!node) in mas_alloc_nodes()
1260 node->slot[0] = mas->alloc; in mas_alloc_nodes()
1261 node->node_count = 1; in mas_alloc_nodes()
1263 node->node_count = 0; in mas_alloc_nodes()
1266 mas->alloc = node; in mas_alloc_nodes()
1267 node->total = ++allocated; in mas_alloc_nodes()
1268 node->request_count = 0; in mas_alloc_nodes()
1272 node = mas->alloc; in mas_alloc_nodes()
1274 max_req = MAPLE_ALLOC_SLOTS - node->node_count; in mas_alloc_nodes()
1275 slots = (void **)&node->slot[node->node_count]; in mas_alloc_nodes()
1281 if (node->node_count == 0) { in mas_alloc_nodes()
1282 node->slot[0]->node_count = 0; in mas_alloc_nodes()
1283 node->slot[0]->request_count = 0; in mas_alloc_nodes()
1286 node->node_count += count; in mas_alloc_nodes()
1290 node = node->slot[0]; in mas_alloc_nodes()
1291 } while (unlikely(node->node_count == MAPLE_ALLOC_SLOTS)); in mas_alloc_nodes()
1382 mas->node = mte_safe_root(root); in mas_start()
1384 if (mte_dead_node(mas->node)) in mas_start()
1390 mas->node = NULL; in mas_start()
1422 static __always_inline unsigned char ma_data_end(struct maple_node *node, in ma_data_end() argument
1431 return ma_meta_end(node, type); in ma_data_end()
1435 return ma_meta_end(node, type); in ma_data_end()
1455 struct maple_node *node; in mas_data_end() local
1459 type = mte_node_type(mas->node); in mas_data_end()
1460 node = mas_mn(mas); in mas_data_end()
1462 return ma_meta_end(node, type); in mas_data_end()
1464 pivots = ma_pivots(node, type); in mas_data_end()
1465 if (unlikely(ma_dead_node(node))) in mas_data_end()
1470 return ma_meta_end(node, type); in mas_data_end()
1494 mt = mte_node_type(mas->node); in mas_leaf_max_gap()
1569 ma_max_gap(struct maple_node *node, unsigned long *gaps, enum maple_type mt, in ma_max_gap() argument
1575 i = offset = ma_meta_end(node, mt); in ma_max_gap()
1598 struct maple_node *node; in mas_max_gap() local
1600 mt = mte_node_type(mas->node); in mas_max_gap()
1604 node = mas_mn(mas); in mas_max_gap()
1606 offset = ma_meta_gap(node); in mas_max_gap()
1607 gaps = ma_gaps(node, mt); in mas_max_gap()
1630 pnode = mte_parent(mas->node); in mas_parent_gap()
1631 pmt = mas_parent_type(mas, mas->node); in mas_parent_gap()
1680 if (mte_is_root(mas->node)) in mas_update_gap()
1685 pslot = mte_parent_slot(mas->node); in mas_update_gap()
1686 p_gap = ma_gaps(mte_parent(mas->node), in mas_update_gap()
1687 mas_parent_type(mas, mas->node))[pslot]; in mas_update_gap()
1703 struct maple_node *node = mte_to_node(parent); in mas_adopt_children() local
1704 void __rcu **slots = ma_slots(node, type); in mas_adopt_children()
1705 unsigned long *pivots = ma_pivots(node, type); in mas_adopt_children()
1709 offset = ma_data_end(node, type, pivots, mas->max); in mas_adopt_children()
1730 if (mte_is_root(mas->node)) { in mas_put_in_tree()
1732 rcu_assign_pointer(mas->tree->ma_root, mte_mk_root(mas->node)); in mas_put_in_tree()
1736 offset = mte_parent_slot(mas->node); in mas_put_in_tree()
1737 slots = ma_slots(mte_parent(mas->node), in mas_put_in_tree()
1738 mas_parent_type(mas, mas->node)); in mas_put_in_tree()
1739 rcu_assign_pointer(slots[offset], mas->node); in mas_put_in_tree()
1774 struct maple_node *node; in mas_find_child() local
1777 mt = mte_node_type(mas->node); in mas_find_child()
1778 node = mas_mn(mas); in mas_find_child()
1779 slots = ma_slots(node, mt); in mas_find_child()
1780 pivots = ma_pivots(node, mt); in mas_find_child()
1781 end = ma_data_end(node, mt, pivots, mas->max); in mas_find_child()
1784 if (mte_parent(entry) == node) { in mas_find_child()
1933 struct maple_node *node; in mas_mab_cp() local
1939 node = mas_mn(mas); in mas_mab_cp()
1940 mt = mte_node_type(mas->node); in mas_mab_cp()
1941 pivots = ma_pivots(node, mt); in mas_mab_cp()
1964 slots = ma_slots(node, mt); in mas_mab_cp()
1967 gaps = ma_gaps(node, mt); in mas_mab_cp()
1979 static inline void mas_leaf_set_meta(struct maple_node *node, in mas_leaf_set_meta() argument
1983 ma_set_meta(node, mt, 0, end); in mas_leaf_set_meta()
1998 enum maple_type mt = mte_node_type(mas->node); in mab_mas_cp()
1999 struct maple_node *node = mte_to_node(mas->node); in mab_mas_cp() local
2000 void __rcu **slots = ma_slots(node, mt); in mab_mas_cp()
2001 unsigned long *pivots = ma_pivots(node, mt); in mab_mas_cp()
2027 gaps = ma_gaps(node, mt); in mab_mas_cp()
2036 ma_set_meta(node, mt, offset, end); in mab_mas_cp()
2038 mas_leaf_set_meta(node, mt, end); in mab_mas_cp()
2054 if (mte_is_root(mas->node)) in mas_bulk_rebalance()
2146 unsigned int p_slot = mte_parent_slot(mas->node); in mas_prev_sibling()
2168 if (mte_is_root(mas->node)) in mas_next_sibling()
2173 parent.offset = mte_parent_slot(mas->node) + 1; in mas_next_sibling()
2193 mas->node = enode; in mas_node_or_none()
2196 mas->node = NULL; in mas_node_or_none()
2220 wr_mas->node = mas_mn(wr_mas->mas); in mas_wr_node_walk()
2221 wr_mas->pivots = ma_pivots(wr_mas->node, wr_mas->type); in mas_wr_node_walk()
2222 count = mas->end = ma_data_end(wr_mas->node, wr_mas->type, in mas_wr_node_walk()
2242 mas_mab_cp(mast->orig_r, 0, mt_slot_count(mast->orig_r->node), in mast_rebalance_next()
2304 } while (!mte_is_root(mast->orig_r->node)); in mast_spanning_rebalance()
2330 wr_mas.type = mte_node_type(mast->orig_r->node); in mast_ascend()
2336 wr_mas.type = mte_node_type(mast->orig_l->node); in mast_ascend()
2436 mas_set_parent(mas, mas->node, left, *slot); in mas_set_split_parent()
2438 mas_set_parent(mas, mas->node, right, (*slot) - split - 1); in mas_set_split_parent()
2523 enode = tmp_mas->node; in mas_topiary_node()
2566 while (!mte_is_leaf(tmp[0].node)) { in mas_topiary_replace()
2578 mas_adopt_children(&tmp[i], tmp[i].node); in mas_topiary_replace()
2597 tmp[0].node = old_enode; in mas_topiary_replace()
2613 mat_add(&subtrees, tmp_next[n].node); in mas_topiary_replace()
2631 } while (!mte_is_leaf(tmp[0].node)); in mas_topiary_replace()
2653 if (mte_is_leaf(mas->node)) in mas_wmb_replace()
2725 mt_slot_count(mast->orig_r->node), mast->bn, in mast_combine_cp_right()
2737 if (mast->bn->b_end > mt_min_slot_count(mast->orig_l->node)) in mast_sufficient()
2750 if (mast->bn->b_end > mt_slot_count(mast->orig_l->node)) in mast_overflow()
2760 struct maple_node *node; in mtree_range_walk() local
2768 next = mas->node; in mtree_range_walk()
2773 node = mte_to_node(next); in mtree_range_walk()
2775 pivots = ma_pivots(node, type); in mtree_range_walk()
2776 end = ma_data_end(node, type, pivots, max); in mtree_range_walk()
2796 slots = ma_slots(node, type); in mtree_range_walk()
2798 if (unlikely(ma_dead_node(node))) in mtree_range_walk()
2808 mas->node = last; in mtree_range_walk()
2872 mast->bn->type = mte_node_type(mast->orig_l->node); in mas_spanning_rebalance()
2906 if (mast->orig_l->node == mast->orig_r->node) { in mas_spanning_rebalance()
2929 l_mas.node = mt_mk_node(ma_mnode_ptr(mas_pop_node(mas)), in mas_spanning_rebalance()
2930 mte_node_type(mast->orig_l->node)); in mas_spanning_rebalance()
2934 mas_set_parent(mas, left, l_mas.node, slot); in mas_spanning_rebalance()
2936 mas_set_parent(mas, middle, l_mas.node, ++slot); in mas_spanning_rebalance()
2939 mas_set_parent(mas, right, l_mas.node, ++slot); in mas_spanning_rebalance()
2944 while (!mte_is_root(mast->orig_l->node)) in mas_spanning_rebalance()
2950 old_enode = mast->orig_l->node; in mas_spanning_rebalance()
2952 mas->node = l_mas.node; in mas_spanning_rebalance()
2994 mast.bn->type = mte_node_type(mas->node); in mas_rebalance()
2999 mas_mab_cp(&r_mas, 0, mt_slot_count(r_mas.node), b_node, b_end); in mas_rebalance()
3025 enum maple_type mt = mte_node_type(mas->node); in mas_destroy_rebalance()
3026 struct maple_node reuse, *newnode, *parent, *new_left, *left, *node; in mas_destroy_rebalance() local
3046 node = mas_mn(mas); in mas_destroy_rebalance()
3047 newnode->parent = node->parent; in mas_destroy_rebalance()
3060 memcpy(slots + tmp, ma_slots(node, mt), sizeof(void *) * end); in mas_destroy_rebalance()
3061 memcpy(pivs + tmp, ma_pivots(node, mt), sizeof(unsigned long) * end); in mas_destroy_rebalance()
3065 old_eparent = mt_mk_node(mte_parent(l_mas.node), in mas_destroy_rebalance()
3066 mas_parent_type(&l_mas, l_mas.node)); in mas_destroy_rebalance()
3079 memcpy(node, newnode, sizeof(struct maple_node)); in mas_destroy_rebalance()
3080 ma_set_meta(node, mt, 0, tmp - 1); in mas_destroy_rebalance()
3081 mte_set_pivot(old_eparent, mte_parent_slot(l_mas.node), in mas_destroy_rebalance()
3095 mas->node = mt_mk_node(newnode, mt); in mas_destroy_rebalance()
3100 mt = mte_node_type(l_mas.node); in mas_destroy_rebalance()
3106 l_mas.node = mt_mk_node(new_left, mt); in mas_destroy_rebalance()
3109 offset = mte_parent_slot(mas->node); in mas_destroy_rebalance()
3110 mt = mas_parent_type(&l_mas, l_mas.node); in mas_destroy_rebalance()
3115 rcu_assign_pointer(slots[offset], mas->node); in mas_destroy_rebalance()
3116 rcu_assign_pointer(slots[offset - 1], l_mas.node); in mas_destroy_rebalance()
3121 mte_set_gap(eparent, mte_parent_slot(mas->node), gap); in mas_destroy_rebalance()
3123 mte_set_gap(eparent, mte_parent_slot(l_mas.node), gap); in mas_destroy_rebalance()
3128 mas_adopt_children(mas, mas->node); in mas_destroy_rebalance()
3144 if (mte_is_root(mas->node)) { in mas_split_final_node()
3155 mas_set_parent(mas, mast->l->node, ancestor, mast->l->offset); in mas_split_final_node()
3156 mas_set_parent(mas, mast->r->node, ancestor, mast->r->offset); in mas_split_final_node()
3159 mast->l->node = ancestor; in mas_split_final_node()
3179 if (mte_is_root(mas->node)) { in mast_fill_bnode()
3183 mas->offset = mte_parent_slot(mas->node); in mast_fill_bnode()
3190 mab_set_b_end(mast->bn, mast->l, mast->l->node); in mast_fill_bnode()
3192 mab_set_b_end(mast->bn, mast->r, mast->r->node); in mast_fill_bnode()
3197 mas_mab_cp(mas, split + skip, mt_slot_count(mas->node) - 1, in mast_fill_bnode()
3201 mast->bn->type = mte_node_type(mas->node); in mast_fill_bnode()
3217 mte_set_pivot(mast->r->node, 0, mast->r->max); in mast_split_data()
3219 mast->l->offset = mte_parent_slot(mas->node); in mast_split_data()
3222 if (mte_is_leaf(mas->node)) in mast_split_data()
3226 mas_set_split_parent(mast->orig_l, mast->l->node, mast->r->node, in mast_split_data()
3228 mas_set_split_parent(mast->orig_r, mast->l->node, mast->r->node, in mast_split_data()
3260 space = 2 * mt_slot_count(mas->node) - 2; in mas_push_data()
3287 tmp_mas.node = mast->l->node; in mas_push_data()
3290 tmp_mas.node = mast->r->node; in mas_push_data()
3355 l_mas.node = mas_new_ma_node(mas, b_node); in mas_split()
3356 r_mas.node = mas_new_ma_node(mas, b_node); in mas_split()
3388 old = mas->node; in mas_split()
3389 mas->node = l_mas.node; in mas_split()
3422 struct maple_node *node; in mas_root_expand() local
3427 node = mas_pop_node(mas); in mas_root_expand()
3428 pivots = ma_pivots(node, type); in mas_root_expand()
3429 slots = ma_slots(node, type); in mas_root_expand()
3430 node->parent = ma_parent_ptr(mas_tree_parent(mas)); in mas_root_expand()
3431 mas->node = mt_mk_node(node, type); in mas_root_expand()
3450 ma_set_meta(node, maple_leaf_64, 0, slot); in mas_root_expand()
3452 rcu_assign_pointer(mas->tree->ma_root, mte_mk_root(mas->node)); in mas_root_expand()
3521 wr_mas->type = mte_node_type(wr_mas->mas->node); in mas_wr_walk_descend()
3523 wr_mas->slots = ma_slots(wr_mas->node, wr_mas->type); in mas_wr_walk_descend()
3530 wr_mas->mas->node = wr_mas->content; in mas_wr_walk_traverse()
3652 struct maple_node *node; in mtree_lookup_walk() local
3658 next = mas->node; in mtree_lookup_walk()
3660 node = mte_to_node(next); in mtree_lookup_walk()
3662 pivots = ma_pivots(node, type); in mtree_lookup_walk()
3670 slots = ma_slots(node, type); in mtree_lookup_walk()
3672 if (unlikely(ma_dead_node(node))) in mtree_lookup_walk()
3696 struct maple_node *node; in mas_new_root() local
3709 node = mas_pop_node(mas); in mas_new_root()
3710 pivots = ma_pivots(node, type); in mas_new_root()
3711 slots = ma_slots(node, type); in mas_new_root()
3712 node->parent = ma_parent_ptr(mas_tree_parent(mas)); in mas_new_root()
3713 mas->node = mt_mk_node(node, type); in mas_new_root()
3718 rcu_assign_pointer(mas->tree->ma_root, mte_mk_root(mas->node)); in mas_new_root()
3890 struct maple_enode *old_enode = mas->node; in mas_wr_node_store()
3892 mas->node = mt_mk_node(newnode, wr_mas->type); in mas_wr_node_store()
3895 memcpy(wr_mas->node, newnode, sizeof(struct maple_node)); in mas_wr_node_store()
4033 ma_set_meta(wr_mas->node, wr_mas->type, 0, new_end); in mas_wr_append()
4158 if (mte_is_leaf(mas->node) && mas->last == mas->max) in mas_wr_prealloc_setup()
4258 if (!mte_is_root(mas->node) && !(mas->mas_flags & MA_STATE_BULK)) in mas_wr_store_type()
4391 return xa_err(mas->node); in mas_alloc_cyclic()
4413 struct maple_node *node, const unsigned long index) in mas_rewalk_if_dead() argument
4415 if (unlikely(ma_dead_node(node))) { in mas_rewalk_if_dead()
4438 struct maple_node *node; in mas_prev_node() local
4442 node = mas_mn(mas); in mas_prev_node()
4452 if (ma_is_root(node)) in mas_prev_node()
4460 node = mas_mn(mas); in mas_prev_node()
4464 mt = mte_node_type(mas->node); in mas_prev_node()
4467 slots = ma_slots(node, mt); in mas_prev_node()
4468 mas->node = mas_slot(mas, slots, offset); in mas_prev_node()
4469 if (unlikely(ma_dead_node(node))) in mas_prev_node()
4472 mt = mte_node_type(mas->node); in mas_prev_node()
4473 node = mas_mn(mas); in mas_prev_node()
4474 pivots = ma_pivots(node, mt); in mas_prev_node()
4475 offset = ma_data_end(node, mt, pivots, max); in mas_prev_node()
4476 if (unlikely(ma_dead_node(node))) in mas_prev_node()
4480 slots = ma_slots(node, mt); in mas_prev_node()
4481 mas->node = mas_slot(mas, slots, offset); in mas_prev_node()
4482 pivots = ma_pivots(node, mt); in mas_prev_node()
4483 if (unlikely(ma_dead_node(node))) in mas_prev_node()
4490 if (unlikely(mte_dead_node(mas->node))) in mas_prev_node()
4497 if (unlikely(ma_dead_node(node))) in mas_prev_node()
4520 struct maple_node *node; in mas_prev_slot() local
4524 node = mas_mn(mas); in mas_prev_slot()
4525 type = mte_node_type(mas->node); in mas_prev_slot()
4526 pivots = ma_pivots(node, type); in mas_prev_slot()
4527 if (unlikely(mas_rewalk_if_dead(mas, node, save_point))) in mas_prev_slot()
4533 if (unlikely(mas_rewalk_if_dead(mas, node, save_point))) in mas_prev_slot()
4558 node = mas_mn(mas); in mas_prev_slot()
4559 type = mte_node_type(mas->node); in mas_prev_slot()
4560 pivots = ma_pivots(node, type); in mas_prev_slot()
4564 slots = ma_slots(node, type); in mas_prev_slot()
4566 if (unlikely(mas_rewalk_if_dead(mas, node, save_point))) in mas_prev_slot()
4596 static int mas_next_node(struct ma_state *mas, struct maple_node *node, in mas_next_node() argument
4614 if (ma_is_root(node)) in mas_next_node()
4622 node = mas_mn(mas); in mas_next_node()
4623 mt = mte_node_type(mas->node); in mas_next_node()
4624 pivots = ma_pivots(node, mt); in mas_next_node()
4625 node_end = ma_data_end(node, mt, pivots, mas->max); in mas_next_node()
4626 if (unlikely(ma_dead_node(node))) in mas_next_node()
4631 slots = ma_slots(node, mt); in mas_next_node()
4634 if (unlikely(ma_dead_node(node))) in mas_next_node()
4642 mas->node = enode; in mas_next_node()
4643 node = mas_mn(mas); in mas_next_node()
4644 mt = mte_node_type(mas->node); in mas_next_node()
4645 slots = ma_slots(node, mt); in mas_next_node()
4647 if (unlikely(ma_dead_node(node))) in mas_next_node()
4652 pivots = ma_pivots(node, mt); in mas_next_node()
4659 if (unlikely(ma_dead_node(node))) in mas_next_node()
4662 mas->node = enode; in mas_next_node()
4667 if (unlikely(ma_dead_node(node))) in mas_next_node()
4689 struct maple_node *node; in mas_next_slot() local
4694 node = mas_mn(mas); in mas_next_slot()
4695 type = mte_node_type(mas->node); in mas_next_slot()
4696 pivots = ma_pivots(node, type); in mas_next_slot()
4697 if (unlikely(mas_rewalk_if_dead(mas, node, save_point))) in mas_next_slot()
4706 if (unlikely(mas_rewalk_if_dead(mas, node, save_point))) in mas_next_slot()
4729 if (mas_next_node(mas, node, max)) { in mas_next_slot()
4739 node = mas_mn(mas); in mas_next_slot()
4740 type = mte_node_type(mas->node); in mas_next_slot()
4741 pivots = ma_pivots(node, type); in mas_next_slot()
4745 slots = ma_slots(node, type); in mas_next_slot()
4747 if (unlikely(mas_rewalk_if_dead(mas, node, save_point))) in mas_next_slot()
4779 enum maple_type type = mte_node_type(mas->node); in mas_rev_awalk()
4780 struct maple_node *node = mas_mn(mas); in mas_rev_awalk() local
4796 pivots = ma_pivots(node, type); in mas_rev_awalk()
4797 slots = ma_slots(node, type); in mas_rev_awalk()
4798 gaps = ma_gaps(node, type); in mas_rev_awalk()
4848 mas->node = mas_slot(mas, slots, offset); in mas_rev_awalk()
4855 if (!mte_is_root(mas->node)) in mas_rev_awalk()
4865 enum maple_type type = mte_node_type(mas->node); in mas_anode_descend()
4870 struct maple_node *node; in mas_anode_descend() local
4878 node = mas_mn(mas); in mas_anode_descend()
4879 pivots = ma_pivots(node, type); in mas_anode_descend()
4880 slots = ma_slots(node, type); in mas_anode_descend()
4881 gaps = ma_gaps(node, type); in mas_anode_descend()
4884 data_end = ma_data_end(node, type, pivots, mas->max); in mas_anode_descend()
4905 mas->node = mas_slot(mas, slots, offset); in mas_anode_descend()
4966 if (mte_is_root(mas->node)) { in mas_rewind_node()
4992 if (mte_is_root(mas->node)) { in mas_skip_node()
5026 if (last == mas->node) in mas_awalk()
5029 last = mas->node; in mas_awalk()
5080 struct maple_node *node; in mas_empty_area() local
5105 return xa_err(mas->node); in mas_empty_area()
5108 node = mas_mn(mas); in mas_empty_area()
5109 mt = mte_node_type(mas->node); in mas_empty_area()
5110 pivots = ma_pivots(node, mt); in mas_empty_area()
5115 mas->end = ma_data_end(node, mt, pivots, mas->max); in mas_empty_area()
5131 struct maple_enode *last = mas->node; in mas_empty_area_rev()
5157 if (last == mas->node) { in mas_empty_area_rev()
5161 last = mas->node; in mas_empty_area_rev()
5166 return xa_err(mas->node); in mas_empty_area_rev()
5195 struct maple_node *node; in mte_dead_leaves() local
5203 node = mte_to_node(entry); in mte_dead_leaves()
5205 if (!node || !type) in mte_dead_leaves()
5209 node->type = type; in mte_dead_leaves()
5210 rcu_assign_pointer(slots[offset], node); in mte_dead_leaves()
5225 struct maple_node *node, *next; in mte_dead_walk() local
5231 node = mte_to_node(*enode); in mte_dead_walk()
5232 slots = ma_slots(node, node->type); in mte_dead_walk()
5250 struct maple_node *node, *start; in mt_free_walk() local
5255 node = container_of(head, struct maple_node, rcu); in mt_free_walk()
5257 if (ma_is_leaf(node->type)) in mt_free_walk()
5260 start = node; in mt_free_walk()
5261 enode = mt_mk_node(node, node->type); in mt_free_walk()
5263 node = mte_to_node(enode); in mt_free_walk()
5265 mt_free_bulk(node->slot_len, slots); in mt_free_walk()
5266 offset = node->parent_slot + 1; in mt_free_walk()
5267 enode = node->piv_parent; in mt_free_walk()
5268 if (mte_to_node(enode) == node) in mt_free_walk()
5277 node = mte_to_node(enode); in mt_free_walk()
5278 } while ((node != start) || (node->slot_len < offset)); in mt_free_walk()
5280 slots = ma_slots(node, node->type); in mt_free_walk()
5281 mt_free_bulk(node->slot_len, slots); in mt_free_walk()
5284 mt_free_rcu(&node->rcu); in mt_free_walk()
5290 struct maple_node *node; in mte_destroy_descend() local
5298 node = mte_to_node(*enode); in mte_destroy_descend()
5300 slots = ma_slots(node, type); in mte_destroy_descend()
5306 node->type = type; in mte_destroy_descend()
5307 node->piv_parent = prev; in mte_destroy_descend()
5308 node->parent_slot = offset; in mte_destroy_descend()
5321 struct maple_node *node = mte_to_node(enode); in mt_destroy_walk() local
5326 node->type = mte_node_type(enode); in mt_destroy_walk()
5332 node = mte_to_node(enode); // Updated in the above call. in mt_destroy_walk()
5338 node->slot_len = mte_dead_leaves(enode, mt, slots); in mt_destroy_walk()
5340 mt_free_bulk(node->slot_len, slots); in mt_destroy_walk()
5341 offset = node->parent_slot + 1; in mt_destroy_walk()
5342 enode = node->piv_parent; in mt_destroy_walk()
5343 if (mte_to_node(enode) == node) in mt_destroy_walk()
5358 node = mte_to_node(enode); in mt_destroy_walk()
5361 node = mte_to_node(enode); in mt_destroy_walk()
5362 node->slot_len = mte_dead_leaves(enode, mt, slots); in mt_destroy_walk()
5364 mt_free_bulk(node->slot_len, slots); in mt_destroy_walk()
5368 mt_free_rcu(&node->rcu); in mt_destroy_walk()
5370 mt_clear_meta(mt, node, node->type); in mt_destroy_walk()
5383 struct maple_node *node = mte_to_node(enode); in mte_destroy_walk() local
5387 call_rcu(&node->rcu, mt_free_walk); in mte_destroy_walk()
5475 ret = xa_err(mas->node); in mas_store_gfp()
5540 ret = xa_err(mas->node); in mas_preallocate()
5562 struct maple_alloc *node; in mas_destroy() local
5578 if (end < mt_min_slot_count(mas->node) - 1) in mas_destroy()
5587 node = mas->alloc; in mas_destroy()
5588 mas->alloc = node->slot[0]; in mas_destroy()
5589 if (node->node_count > 1) { in mas_destroy()
5590 size_t count = node->node_count - 1; in mas_destroy()
5592 mt_free_bulk(count, (void __rcu **)&node->slot[1]); in mas_destroy()
5595 mt_free_one(ma_mnode_ptr(node)); in mas_destroy()
5618 struct maple_enode *enode = mas->node; in mas_expected_entries()
5657 ret = xa_err(mas->node); in mas_expected_entries()
5658 mas->node = enode; in mas_expected_entries()
5667 if (!mas->node) { in mas_may_activate()
5951 mas->node = NULL; in mas_pause()
6285 if (likely(mas->node != MA_ERROR(-ENOMEM))) in mas_nomem()
6428 ret = xa_err(ms.node); in mtree_insert_range()
6480 ret = xa_err(mas.node); in mtree_alloc_range()
6562 ret = xa_err(mas.node); in mtree_alloc_rrange()
6609 struct maple_node *node; in mas_dup_free() local
6618 while (!mte_is_root(mas->node)) { in mas_dup_free()
6625 } while (!mte_is_leaf(mas->node)); in mas_dup_free()
6630 node = mte_to_node(mas->node); in mas_dup_free()
6631 type = mte_node_type(mas->node); in mas_dup_free()
6632 slots = ma_slots(node, type); in mas_dup_free()
6639 node = mte_to_node(mas->node); in mas_dup_free()
6640 mt_free_one(node); in mas_dup_free()
6655 struct maple_node *node = mte_to_node(mas->node); in mas_copy_node() local
6656 struct maple_node *new_node = mte_to_node(new_mas->node); in mas_copy_node()
6660 memcpy(new_node, node, sizeof(struct maple_node)); in mas_copy_node()
6662 val = (unsigned long)node->parent & MAPLE_NODE_MASK; in mas_copy_node()
6678 struct maple_node *node = mte_to_node(mas->node); in mas_dup_alloc() local
6679 struct maple_node *new_node = mte_to_node(new_mas->node); in mas_dup_alloc()
6687 type = mte_node_type(mas->node); in mas_dup_alloc()
6698 slots = ma_slots(node, type); in mas_dup_alloc()
6722 struct maple_node *node; in mas_dup_build() local
6737 node = mt_alloc_one(gfp); in mas_dup_build()
6738 if (!node) { in mas_dup_build()
6744 type = mte_node_type(mas->node); in mas_dup_build()
6745 root = mt_mk_node(node, type); in mas_dup_build()
6746 new_mas->node = root; in mas_dup_build()
6752 if (!mte_is_leaf(mas->node)) { in mas_dup_build()
6777 parent = ma_parent_ptr(mte_to_node(new_mas->node)); in mas_dup_build()
6820 ret = xa_err(mas.node); in __mt_dup()
6860 ret = xa_err(mas.node); in mtree_dup()
7068 return mas_slot(mas, ma_slots(mas_mn(mas), mte_node_type(mas->node)), in mas_get_slot()
7076 struct maple_enode *p, *mn = mas->node; in mas_dfs_postorder()
7086 mas->node = mn; in mas_dfs_postorder()
7089 p = mas->node; in mas_dfs_postorder()
7095 mas->node = p; in mas_dfs_postorder()
7144 struct maple_range_64 *node = &mte_to_node(entry)->mr64; in mt_dump_range64() local
7153 pr_cont(PTR_FMT " %lX ", node->slot[i], node->pivot[i]); in mt_dump_range64()
7156 pr_cont(PTR_FMT " %lu ", node->slot[i], node->pivot[i]); in mt_dump_range64()
7159 pr_cont(PTR_FMT "\n", node->slot[i]); in mt_dump_range64()
7164 last = node->pivot[i]; in mt_dump_range64()
7165 else if (!node->slot[i] && max != mt_node_max(entry)) in mt_dump_range64()
7170 mt_dump_entry(mt_slot(mt, node->slot, i), in mt_dump_range64()
7172 else if (node->slot[i]) in mt_dump_range64()
7173 mt_dump_node(mt, mt_slot(mt, node->slot, i), in mt_dump_range64()
7182 node, last, max, i); in mt_dump_range64()
7186 node, last, max, i); in mt_dump_range64()
7197 struct maple_arange_64 *node = &mte_to_node(entry)->ma64; in mt_dump_arange64() local
7205 pr_cont("%lx ", node->gap[i]); in mt_dump_arange64()
7208 pr_cont("%lu ", node->gap[i]); in mt_dump_arange64()
7211 pr_cont("| %02X %02X| ", node->meta.end, node->meta.gap); in mt_dump_arange64()
7215 pr_cont(PTR_FMT " %lX ", node->slot[i], node->pivot[i]); in mt_dump_arange64()
7218 pr_cont(PTR_FMT " %lu ", node->slot[i], node->pivot[i]); in mt_dump_arange64()
7221 pr_cont(PTR_FMT "\n", node->slot[i]); in mt_dump_arange64()
7226 last = node->pivot[i]; in mt_dump_arange64()
7227 else if (!node->slot[i]) in mt_dump_arange64()
7231 if (node->slot[i]) in mt_dump_arange64()
7232 mt_dump_node(mt, mt_slot(mt, node->slot, i), in mt_dump_arange64()
7241 node, last, max, i); in mt_dump_arange64()
7245 node, last, max, i); in mt_dump_arange64()
7256 struct maple_node *node = mte_to_node(entry); in mt_dump_node() local
7262 pr_cont("node " PTR_FMT " depth %d type %d parent " PTR_FMT, node, in mt_dump_node()
7263 depth, type, node ? node->parent : NULL); in mt_dump_node()
7270 mt_dump_entry(mt_slot(mt, node->slot, i), in mt_dump_node()
7308 struct maple_enode *mte = mas->node; in mas_validate_gaps()
7309 struct maple_node *p_mn, *node = mte_to_node(mte); in mas_validate_gaps() local
7310 enum maple_type mt = mte_node_type(mas->node); in mas_validate_gaps()
7315 unsigned long *pivots = ma_pivots(node, mt); in mas_validate_gaps()
7331 gaps = ma_gaps(node, mt); in mas_validate_gaps()
7363 offset = ma_meta_gap(node); in mas_validate_gaps()
7365 pr_err("gap offset " PTR_FMT "[%u] is invalid\n", node, offset); in mas_validate_gaps()
7371 node, offset, max_gap); in mas_validate_gaps()
7378 node, i); in mas_validate_gaps()
7387 p_slot = mte_parent_slot(mas->node); in mas_validate_gaps()
7400 struct maple_enode *node; in mas_validate_parent_slot() local
7406 if (mte_is_root(mas->node)) in mas_validate_parent_slot()
7409 p_slot = mte_parent_slot(mas->node); in mas_validate_parent_slot()
7410 p_type = mas_parent_type(mas, mas->node); in mas_validate_parent_slot()
7411 parent = mte_parent(mas->node); in mas_validate_parent_slot()
7418 node = mas_slot(mas, slots, i); in mas_validate_parent_slot()
7420 if (node != mas->node) in mas_validate_parent_slot()
7423 MT_BUG_ON(mas->tree, node != mas->node); in mas_validate_parent_slot()
7424 } else if (node == mas->node) { in mas_validate_parent_slot()
7427 MT_BUG_ON(mas->tree, node == mas->node); in mas_validate_parent_slot()
7434 enum maple_type type = mte_node_type(mas->node); in mas_validate_child_slot()
7435 void __rcu **slots = ma_slots(mte_to_node(mas->node), type); in mas_validate_child_slot()
7436 unsigned long *pivots = ma_pivots(mte_to_node(mas->node), type); in mas_validate_child_slot()
7440 if (mte_is_leaf(mas->node)) in mas_validate_child_slot()
7459 if (mte_parent(child) != mte_to_node(mas->node)) { in mas_validate_child_slot()
7462 mte_to_node(mas->node)); in mas_validate_child_slot()
7480 enum maple_type type = mte_node_type(mas->node); in mas_validate_limits()
7481 void __rcu **slots = ma_slots(mte_to_node(mas->node), type); in mas_validate_limits()
7555 while (!mte_is_leaf(mas.node)) in mt_validate_nulls()
7558 slots = ma_slots(mte_to_node(mas.node), mte_node_type(mas.node)); in mt_validate_nulls()
7572 slots = ma_slots(mte_to_node(mas.node), in mt_validate_nulls()
7573 mte_node_type(mas.node)); in mt_validate_nulls()
7596 while (!mte_is_leaf(mas.node)) in mt_validate()
7600 MAS_WARN_ON(&mas, mte_dead_node(mas.node)); in mt_validate()
7602 if (MAS_WARN_ON(&mas, (end < mt_min_slot_count(mas.node)) && in mt_validate()
7603 (!mte_is_root(mas.node)))) { in mt_validate()
7622 mas->tree, mas->node); in mas_dump()
7696 wr_mas->node, wr_mas->r_min, wr_mas->r_max); in mas_wr_dump()