Lines Matching refs:mas
193 static void mas_set_height(struct ma_state *mas) in mas_set_height() argument
195 unsigned int new_flags = mas->tree->ma_flags; in mas_set_height()
198 MAS_BUG_ON(mas, mas->depth > MAPLE_HEIGHT_MAX); in mas_set_height()
199 new_flags |= mas->depth << MT_FLAGS_HEIGHT_OFFSET; in mas_set_height()
200 mas->tree->ma_flags = new_flags; in mas_set_height()
203 static unsigned int mas_mt_height(struct ma_state *mas) in mas_mt_height() argument
205 return mt_height(mas->tree); in mas_mt_height()
239 static inline void mas_set_err(struct ma_state *mas, long err) in mas_set_err() argument
241 mas->node = MA_ERROR(err); in mas_set_err()
244 static inline bool mas_is_ptr(const struct ma_state *mas) in mas_is_ptr() argument
246 return mas->node == MAS_ROOT; in mas_is_ptr()
249 static inline bool mas_is_start(const struct ma_state *mas) in mas_is_start() argument
251 return mas->node == MAS_START; in mas_is_start()
254 bool mas_is_err(struct ma_state *mas) in mas_is_err() argument
256 return xa_is_err(mas->node); in mas_is_err()
259 static __always_inline bool mas_is_overflow(struct ma_state *mas) in mas_is_overflow() argument
261 if (unlikely(mas->node == MAS_OVERFLOW)) in mas_is_overflow()
267 static __always_inline bool mas_is_underflow(struct ma_state *mas) in mas_is_underflow() argument
269 if (unlikely(mas->node == MAS_UNDERFLOW)) in mas_is_underflow()
275 static inline bool mas_searchable(struct ma_state *mas) in mas_searchable() argument
277 if (mas_is_none(mas)) in mas_searchable()
280 if (mas_is_ptr(mas)) in mas_searchable()
309 static inline struct maple_node *mas_mn(const struct ma_state *mas) in mas_mn() argument
311 return mte_to_node(mas->node); in mas_mn()
373 static inline bool mas_is_root_limits(const struct ma_state *mas) in mas_is_root_limits() argument
375 return !mas->min && mas->max == ULONG_MAX; in mas_is_root_limits()
452 enum maple_type mas_parent_type(struct ma_state *mas, struct maple_enode *enode) in mas_parent_type() argument
464 if (mt_is_alloc(mas->tree)) in mas_parent_type()
482 void mas_set_parent(struct ma_state *mas, struct maple_enode *enode, in mas_set_parent() argument
490 MAS_BUG_ON(mas, p_type == maple_dense); in mas_set_parent()
491 MAS_BUG_ON(mas, p_type == maple_leaf_64); in mas_set_parent()
587 static inline unsigned long mas_allocated(const struct ma_state *mas) in mas_allocated() argument
589 if (!mas->alloc || ((unsigned long)mas->alloc & 0x1)) in mas_allocated()
592 return mas->alloc->total; in mas_allocated()
605 static inline void mas_set_alloc_req(struct ma_state *mas, unsigned long count) in mas_set_alloc_req() argument
607 if (!mas->alloc || ((unsigned long)mas->alloc & 0x1)) { in mas_set_alloc_req()
609 mas->alloc = NULL; in mas_set_alloc_req()
611 mas->alloc = (struct maple_alloc *)(((count) << 1U) | 1U); in mas_set_alloc_req()
615 mas->alloc->request_count = count; in mas_set_alloc_req()
628 static inline unsigned int mas_alloc_req(const struct ma_state *mas) in mas_alloc_req() argument
630 if ((unsigned long)mas->alloc & 0x1) in mas_alloc_req()
631 return (unsigned long)(mas->alloc) >> 1; in mas_alloc_req()
632 else if (mas->alloc) in mas_alloc_req()
633 return mas->alloc->request_count; in mas_alloc_req()
689 static inline unsigned long mas_pivot(struct ma_state *mas, unsigned char piv) in mas_pivot() argument
691 struct maple_node *node = mas_mn(mas); in mas_pivot()
692 enum maple_type type = mte_node_type(mas->node); in mas_pivot()
694 if (MAS_WARN_ON(mas, piv >= mt_pivots[type])) { in mas_pivot()
695 mas_set_err(mas, -EIO); in mas_pivot()
722 mas_safe_pivot(const struct ma_state *mas, unsigned long *pivots, in mas_safe_pivot() argument
726 return mas->max; in mas_safe_pivot()
740 mas_safe_min(struct ma_state *mas, unsigned long *pivots, unsigned char offset) in mas_safe_min() argument
745 return mas->min; in mas_safe_min()
828 static inline void *mas_slot_locked(struct ma_state *mas, void __rcu **slots, in mas_slot_locked() argument
831 return mt_slot_locked(mas->tree, slots, offset); in mas_slot_locked()
842 static inline void *mas_slot(struct ma_state *mas, void __rcu **slots, in mas_slot() argument
845 return mt_slot(mas->tree, slots, offset); in mas_slot()
854 static inline void *mas_root(struct ma_state *mas) in mas_root() argument
856 return rcu_dereference_check(mas->tree->ma_root, mt_locked(mas->tree)); in mas_root()
870 static inline void *mas_root_locked(struct ma_state *mas) in mas_root_locked() argument
872 return mt_root_locked(mas->tree); in mas_root_locked()
1011 static void mas_mat_destroy(struct ma_state *mas, struct ma_topiary *mat) in mas_mat_destroy() argument
1015 bool in_rcu = mt_in_rcu(mas->tree); in mas_mat_destroy()
1020 mt_destroy_walk(mat->head, mas->tree, !in_rcu); in mas_mat_destroy()
1032 static inline void mas_descend(struct ma_state *mas) in mas_descend() argument
1039 node = mas_mn(mas); in mas_descend()
1040 type = mte_node_type(mas->node); in mas_descend()
1044 if (mas->offset) in mas_descend()
1045 mas->min = pivots[mas->offset - 1] + 1; in mas_descend()
1046 mas->max = mas_safe_pivot(mas, pivots, mas->offset, type); in mas_descend()
1047 mas->node = mas_slot(mas, slots, mas->offset); in mas_descend()
1077 static int mas_ascend(struct ma_state *mas) in mas_ascend() argument
1089 a_node = mas_mn(mas); in mas_ascend()
1091 mas->offset = 0; in mas_ascend()
1095 p_node = mte_parent(mas->node); in mas_ascend()
1099 a_type = mas_parent_type(mas, mas->node); in mas_ascend()
1100 mas->offset = mte_parent_slot(mas->node); in mas_ascend()
1104 if (p_node != mte_parent(mas->node)) in mas_ascend()
1107 mas->node = a_enode; in mas_ascend()
1110 mas->max = ULONG_MAX; in mas_ascend()
1111 mas->min = 0; in mas_ascend()
1115 if (!mas->min) in mas_ascend()
1118 if (mas->max == ULONG_MAX) in mas_ascend()
1125 a_type = mas_parent_type(mas, p_enode); in mas_ascend()
1152 mas->max = max; in mas_ascend()
1153 mas->min = min; in mas_ascend()
1163 static inline struct maple_node *mas_pop_node(struct ma_state *mas) in mas_pop_node() argument
1165 struct maple_alloc *ret, *node = mas->alloc; in mas_pop_node()
1166 unsigned long total = mas_allocated(mas); in mas_pop_node()
1167 unsigned int req = mas_alloc_req(mas); in mas_pop_node()
1175 mas->alloc = NULL; in mas_pop_node()
1182 mas->alloc = node->slot[0]; in mas_pop_node()
1183 mas->alloc->total = node->total - 1; in mas_pop_node()
1195 mas_set_alloc_req(mas, req); in mas_pop_node()
1210 static inline void mas_push_node(struct ma_state *mas, struct maple_node *used) in mas_push_node() argument
1213 struct maple_alloc *head = mas->alloc; in mas_push_node()
1215 unsigned int requested = mas_alloc_req(mas); in mas_push_node()
1217 count = mas_allocated(mas); in mas_push_node()
1234 mas->alloc = reuse; in mas_push_node()
1237 mas_set_alloc_req(mas, requested - 1); in mas_push_node()
1245 static inline void mas_alloc_nodes(struct ma_state *mas, gfp_t gfp) in mas_alloc_nodes() argument
1248 unsigned long allocated = mas_allocated(mas); in mas_alloc_nodes()
1249 unsigned int requested = mas_alloc_req(mas); in mas_alloc_nodes()
1257 mas_set_alloc_req(mas, 0); in mas_alloc_nodes()
1258 if (mas->mas_flags & MA_STATE_PREALLOC) { in mas_alloc_nodes()
1264 if (!allocated || mas->alloc->node_count == MAPLE_ALLOC_SLOTS) { in mas_alloc_nodes()
1270 node->slot[0] = mas->alloc; in mas_alloc_nodes()
1276 mas->alloc = node; in mas_alloc_nodes()
1281 node = mas->alloc; in mas_alloc_nodes()
1301 mas->alloc->total = allocated; in mas_alloc_nodes()
1308 mas_set_alloc_req(mas, requested); in mas_alloc_nodes()
1309 if (mas->alloc && !(((unsigned long)mas->alloc & 0x1))) in mas_alloc_nodes()
1310 mas->alloc->total = allocated; in mas_alloc_nodes()
1311 mas_set_err(mas, -ENOMEM); in mas_alloc_nodes()
1322 static inline void mas_free(struct ma_state *mas, struct maple_enode *used) in mas_free() argument
1326 if (mt_in_rcu(mas->tree)) in mas_free()
1329 mas_push_node(mas, tmp); in mas_free()
1339 static void mas_node_count_gfp(struct ma_state *mas, int count, gfp_t gfp) in mas_node_count_gfp() argument
1341 unsigned long allocated = mas_allocated(mas); in mas_node_count_gfp()
1344 mas_set_alloc_req(mas, count - allocated); in mas_node_count_gfp()
1345 mas_alloc_nodes(mas, gfp); in mas_node_count_gfp()
1357 static void mas_node_count(struct ma_state *mas, int count) in mas_node_count() argument
1359 return mas_node_count_gfp(mas, count, GFP_NOWAIT | __GFP_NOWARN); in mas_node_count()
1375 static inline struct maple_enode *mas_start(struct ma_state *mas) in mas_start() argument
1377 if (likely(mas_is_start(mas))) { in mas_start()
1380 mas->min = 0; in mas_start()
1381 mas->max = ULONG_MAX; in mas_start()
1384 mas->depth = 0; in mas_start()
1385 root = mas_root(mas); in mas_start()
1388 mas->depth = 1; in mas_start()
1389 mas->node = mte_safe_root(root); in mas_start()
1390 mas->offset = 0; in mas_start()
1391 if (mte_dead_node(mas->node)) in mas_start()
1399 mas->node = MAS_NONE; in mas_start()
1400 mas->offset = MAPLE_NODE_SLOTS; in mas_start()
1405 mas->node = MAS_ROOT; in mas_start()
1406 mas->offset = MAPLE_NODE_SLOTS; in mas_start()
1409 if (mas->index > 0) in mas_start()
1460 static inline unsigned char mas_data_end(struct ma_state *mas) in mas_data_end() argument
1467 type = mte_node_type(mas->node); in mas_data_end()
1468 node = mas_mn(mas); in mas_data_end()
1480 if (likely(pivots[offset] == mas->max)) in mas_data_end()
1492 static unsigned long mas_leaf_max_gap(struct ma_state *mas) in mas_leaf_max_gap() argument
1502 mt = mte_node_type(mas->node); in mas_leaf_max_gap()
1503 mn = mas_mn(mas); in mas_leaf_max_gap()
1528 max_gap = pivots[0] - mas->min + 1; in mas_leaf_max_gap()
1535 max_piv = ma_data_end(mn, mt, pivots, mas->max) - 1; in mas_leaf_max_gap()
1540 if (unlikely(mas->max == ULONG_MAX) && !slots[max_piv + 1]) { in mas_leaf_max_gap()
1598 static inline unsigned long mas_max_gap(struct ma_state *mas) in mas_max_gap() argument
1605 mt = mte_node_type(mas->node); in mas_max_gap()
1607 return mas_leaf_max_gap(mas); in mas_max_gap()
1609 node = mas_mn(mas); in mas_max_gap()
1610 MAS_BUG_ON(mas, mt != maple_arange_64); in mas_max_gap()
1625 static inline void mas_parent_gap(struct ma_state *mas, unsigned char offset, in mas_parent_gap() argument
1635 pnode = mte_parent(mas->node); in mas_parent_gap()
1636 pmt = mas_parent_type(mas, mas->node); in mas_parent_gap()
1641 MAS_BUG_ON(mas, pmt != maple_arange_64); in mas_parent_gap()
1665 pmt = mas_parent_type(mas, penode); in mas_parent_gap()
1676 static inline void mas_update_gap(struct ma_state *mas) in mas_update_gap() argument
1682 if (!mt_is_alloc(mas->tree)) in mas_update_gap()
1685 if (mte_is_root(mas->node)) in mas_update_gap()
1688 max_gap = mas_max_gap(mas); in mas_update_gap()
1690 pslot = mte_parent_slot(mas->node); in mas_update_gap()
1691 p_gap = ma_gaps(mte_parent(mas->node), in mas_update_gap()
1692 mas_parent_type(mas, mas->node))[pslot]; in mas_update_gap()
1695 mas_parent_gap(mas, pslot, max_gap); in mas_update_gap()
1704 static inline void mas_adopt_children(struct ma_state *mas, in mas_adopt_children() argument
1714 offset = ma_data_end(node, type, pivots, mas->max); in mas_adopt_children()
1716 child = mas_slot_locked(mas, slots, offset); in mas_adopt_children()
1717 mas_set_parent(mas, child, parent, offset); in mas_adopt_children()
1727 static inline void mas_put_in_tree(struct ma_state *mas, in mas_put_in_tree() argument
1729 __must_hold(mas->tree->ma_lock) in mas_put_in_tree()
1734 if (mte_is_root(mas->node)) { in mas_put_in_tree()
1735 mas_mn(mas)->parent = ma_parent_ptr(mas_tree_parent(mas)); in mas_put_in_tree()
1736 rcu_assign_pointer(mas->tree->ma_root, mte_mk_root(mas->node)); in mas_put_in_tree()
1737 mas_set_height(mas); in mas_put_in_tree()
1740 offset = mte_parent_slot(mas->node); in mas_put_in_tree()
1741 slots = ma_slots(mte_parent(mas->node), in mas_put_in_tree()
1742 mas_parent_type(mas, mas->node)); in mas_put_in_tree()
1743 rcu_assign_pointer(slots[offset], mas->node); in mas_put_in_tree()
1756 static inline void mas_replace_node(struct ma_state *mas, in mas_replace_node() argument
1758 __must_hold(mas->tree->ma_lock) in mas_replace_node()
1760 mas_put_in_tree(mas, old_enode); in mas_replace_node()
1761 mas_free(mas, old_enode); in mas_replace_node()
1769 static inline bool mas_find_child(struct ma_state *mas, struct ma_state *child) in mas_find_child() argument
1770 __must_hold(mas->tree->ma_lock) in mas_find_child()
1780 mt = mte_node_type(mas->node); in mas_find_child()
1781 node = mas_mn(mas); in mas_find_child()
1784 end = ma_data_end(node, mt, pivots, mas->max); in mas_find_child()
1785 for (offset = mas->offset; offset <= end; offset++) { in mas_find_child()
1786 entry = mas_slot_locked(mas, slots, offset); in mas_find_child()
1788 *child = *mas; in mas_find_child()
1789 mas->offset = offset + 1; in mas_find_child()
1872 static inline int mab_calc_split(struct ma_state *mas, in mab_calc_split() argument
1885 if (unlikely((mas->mas_flags & MA_STATE_BULK))) { in mab_calc_split()
1892 mas->mas_flags |= MA_STATE_REBALANCE; in mab_calc_split()
1942 static inline void mas_mab_cp(struct ma_state *mas, unsigned char mas_start, in mas_mab_cp() argument
1953 node = mas_mn(mas); in mas_mab_cp()
1954 mt = mte_node_type(mas->node); in mas_mab_cp()
1969 if (unlikely(mas->max == b_node->pivot[j])) in mas_mab_cp()
1974 b_node->pivot[j] = mas_safe_pivot(mas, pivots, i, mt); in mas_mab_cp()
1981 if (!ma_is_leaf(mt) && mt_is_alloc(mas->tree)) { in mas_mab_cp()
2000 static inline void mas_leaf_set_meta(struct ma_state *mas, in mas_leaf_set_meta() argument
2008 if (pivots[end] && pivots[end] < mas->max) in mas_leaf_set_meta()
2024 struct ma_state *mas, bool new_max) in mab_mas_cp() argument
2027 enum maple_type mt = mte_node_type(mas->node); in mab_mas_cp()
2028 struct maple_node *node = mte_to_node(mas->node); in mab_mas_cp()
2049 mas->max = b_node->pivot[i - 1]; in mab_mas_cp()
2052 if (likely(!ma_is_leaf(mt) && mt_is_alloc(mas->tree))) { in mab_mas_cp()
2067 mas_leaf_set_meta(mas, node, pivots, mt, end); in mab_mas_cp()
2077 static inline void mas_bulk_rebalance(struct ma_state *mas, unsigned char end, in mas_bulk_rebalance() argument
2080 if (!(mas->mas_flags & MA_STATE_BULK)) in mas_bulk_rebalance()
2083 if (mte_is_root(mas->node)) in mas_bulk_rebalance()
2087 mas->mas_flags &= ~MA_STATE_REBALANCE; in mas_bulk_rebalance()
2108 struct ma_state *mas = wr_mas->mas; in mas_store_b_node() local
2112 slot = mas->offset; in mas_store_b_node()
2115 mas_mab_cp(mas, 0, slot - 1, b_node, 0); in mas_store_b_node()
2119 piv = mas->min - 1; in mas_store_b_node()
2121 if (piv + 1 < mas->index) { in mas_store_b_node()
2125 b_node->gap[b_end] = mas->index - 1 - piv; in mas_store_b_node()
2126 b_node->pivot[b_end++] = mas->index - 1; in mas_store_b_node()
2130 mas->offset = b_end; in mas_store_b_node()
2132 b_node->pivot[b_end] = mas->last; in mas_store_b_node()
2135 if (mas->last >= mas->max) in mas_store_b_node()
2139 piv = mas_safe_pivot(mas, wr_mas->pivots, offset_end, wr_mas->type); in mas_store_b_node()
2140 if (piv > mas->last) { in mas_store_b_node()
2142 mas_bulk_rebalance(mas, b_node->b_end, wr_mas->type); in mas_store_b_node()
2145 wr_mas->content = mas_slot_locked(mas, wr_mas->slots, in mas_store_b_node()
2150 b_node->gap[b_end] = piv - mas->last + 1; in mas_store_b_node()
2159 mas_mab_cp(mas, slot, wr_mas->node_end + 1, b_node, ++b_end); in mas_store_b_node()
2173 static inline bool mas_prev_sibling(struct ma_state *mas) in mas_prev_sibling() argument
2175 unsigned int p_slot = mte_parent_slot(mas->node); in mas_prev_sibling()
2177 if (mte_is_root(mas->node)) in mas_prev_sibling()
2183 mas_ascend(mas); in mas_prev_sibling()
2184 mas->offset = p_slot - 1; in mas_prev_sibling()
2185 mas_descend(mas); in mas_prev_sibling()
2195 static inline bool mas_next_sibling(struct ma_state *mas) in mas_next_sibling() argument
2197 MA_STATE(parent, mas->tree, mas->index, mas->last); in mas_next_sibling()
2199 if (mte_is_root(mas->node)) in mas_next_sibling()
2202 parent = *mas; in mas_next_sibling()
2204 parent.offset = mte_parent_slot(mas->node) + 1; in mas_next_sibling()
2208 *mas = parent; in mas_next_sibling()
2209 mas_descend(mas); in mas_next_sibling()
2237 struct ma_state *mas = wr_mas->mas; in mas_wr_node_walk() local
2241 wr_mas->r_max = wr_mas->r_min = mas->index; in mas_wr_node_walk()
2242 mas->offset = mas->index = mas->min; in mas_wr_node_walk()
2246 wr_mas->node = mas_mn(wr_mas->mas); in mas_wr_node_walk()
2249 wr_mas->pivots, mas->max); in mas_wr_node_walk()
2250 offset = mas->offset; in mas_wr_node_walk()
2252 while (offset < count && mas->index > wr_mas->pivots[offset]) in mas_wr_node_walk()
2255 wr_mas->r_max = offset < count ? wr_mas->pivots[offset] : mas->max; in mas_wr_node_walk()
2256 wr_mas->r_min = mas_safe_min(mas, wr_mas->pivots, offset); in mas_wr_node_walk()
2257 wr_mas->offset_end = mas->offset = offset; in mas_wr_node_walk()
2365 wr_mas.mas = mast->orig_l; in mast_ascend()
2383 *mas_new_ma_node(struct ma_state *mas, struct maple_big_node *b_node) in mas_new_ma_node() argument
2385 return mt_mk_node(ma_mnode_ptr(mas_pop_node(mas)), b_node->type); in mas_new_ma_node()
2400 static inline unsigned char mas_mab_to_node(struct ma_state *mas, in mas_mab_to_node() argument
2408 *left = mas_new_ma_node(mas, b_node); in mas_mab_to_node()
2416 split = mab_calc_split(mas, b_node, mid_split, min); in mas_mab_to_node()
2417 *right = mas_new_ma_node(mas, b_node); in mas_mab_to_node()
2421 *middle = mas_new_ma_node(mas, b_node); in mas_mab_to_node()
2435 struct ma_state *mas, in mab_set_b_end() argument
2442 if (mt_is_alloc(mas->tree)) in mab_set_b_end()
2443 b_node->gap[b_node->b_end] = mas_max_gap(mas); in mab_set_b_end()
2444 b_node->pivot[b_node->b_end++] = mas->max; in mab_set_b_end()
2457 static inline void mas_set_split_parent(struct ma_state *mas, in mas_set_split_parent() argument
2462 if (mas_is_none(mas)) in mas_set_split_parent()
2466 mas_set_parent(mas, mas->node, left, *slot); in mas_set_split_parent()
2468 mas_set_parent(mas, mas->node, right, (*slot) - split - 1); in mas_set_split_parent()
2545 static inline void mas_topiary_node(struct ma_state *mas, in mas_topiary_node() argument
2558 mas_push_node(mas, tmp); in mas_topiary_node()
2578 static inline void mas_topiary_replace(struct ma_state *mas, in mas_topiary_replace() argument
2582 MA_TOPIARY(subtrees, mas->tree); in mas_topiary_replace()
2587 mas_put_in_tree(mas, old_enode); in mas_topiary_replace()
2590 tmp[0] = *mas; in mas_topiary_replace()
2609 if (MAS_WARN_ON(mas, n == 0)) in mas_topiary_replace()
2621 return mas_free(mas, old_enode); in mas_topiary_replace()
2623 tmp[0] = *mas; in mas_topiary_replace()
2628 in_rcu = mt_in_rcu(mas->tree); in mas_topiary_replace()
2649 if (MAS_WARN_ON(mas, n == 0)) in mas_topiary_replace()
2656 mas_topiary_node(mas, tmp[i].node, in_rcu); in mas_topiary_replace()
2662 mas_topiary_node(mas, tmp[i].node, in_rcu); in mas_topiary_replace()
2664 mas_mat_destroy(mas, &subtrees); in mas_topiary_replace()
2674 static inline void mas_wmb_replace(struct ma_state *mas, in mas_wmb_replace() argument
2678 mas_topiary_replace(mas, old_enode); in mas_wmb_replace()
2680 if (mte_is_leaf(mas->node)) in mas_wmb_replace()
2683 mas_update_gap(mas); in mas_wmb_replace()
2783 static inline void *mtree_range_walk(struct ma_state *mas) in mtree_range_walk() argument
2795 next = mas->node; in mtree_range_walk()
2796 min = mas->min; in mtree_range_walk()
2797 max = mas->max; in mtree_range_walk()
2808 if (pivots[offset] >= mas->index) { in mtree_range_walk()
2817 } while ((offset < end) && (pivots[offset] < mas->index)); in mtree_range_walk()
2827 next = mt_slot(mas->tree, slots, offset); in mtree_range_walk()
2832 mas->offset = offset; in mtree_range_walk()
2833 mas->index = min; in mtree_range_walk()
2834 mas->last = max; in mtree_range_walk()
2835 mas->min = prev_min; in mtree_range_walk()
2836 mas->max = prev_max; in mtree_range_walk()
2837 mas->node = last; in mtree_range_walk()
2841 mas_reset(mas); in mtree_range_walk()
2863 static int mas_spanning_rebalance(struct ma_state *mas, in mas_spanning_rebalance() argument
2871 MA_STATE(l_mas, mas->tree, mas->index, mas->index); in mas_spanning_rebalance()
2872 MA_STATE(r_mas, mas->tree, mas->index, mas->last); in mas_spanning_rebalance()
2873 MA_STATE(m_mas, mas->tree, mas->index, mas->index); in mas_spanning_rebalance()
2905 split = mas_mab_to_node(mas, mast->bn, &left, &right, &middle, in mas_spanning_rebalance()
2951 l_mas.node = mt_mk_node(ma_mnode_ptr(mas_pop_node(mas)), in mas_spanning_rebalance()
2955 mas_set_parent(mas, left, l_mas.node, slot); in mas_spanning_rebalance()
2957 mas_set_parent(mas, middle, l_mas.node, ++slot); in mas_spanning_rebalance()
2960 mas_set_parent(mas, right, l_mas.node, ++slot); in mas_spanning_rebalance()
2964 mas_mn(mast->l)->parent = ma_parent_ptr(mas_tree_parent(mas)); in mas_spanning_rebalance()
2972 mas->depth = l_mas.depth; in mas_spanning_rebalance()
2973 mas->node = l_mas.node; in mas_spanning_rebalance()
2974 mas->min = l_mas.min; in mas_spanning_rebalance()
2975 mas->max = l_mas.max; in mas_spanning_rebalance()
2976 mas->offset = l_mas.offset; in mas_spanning_rebalance()
2977 mas_wmb_replace(mas, old_enode); in mas_spanning_rebalance()
2978 mtree_range_walk(mas); in mas_spanning_rebalance()
2992 static inline int mas_rebalance(struct ma_state *mas, in mas_rebalance() argument
2995 char empty_count = mas_mt_height(mas); in mas_rebalance()
2999 MA_STATE(l_mas, mas->tree, mas->index, mas->last); in mas_rebalance()
3000 MA_STATE(r_mas, mas->tree, mas->index, mas->last); in mas_rebalance()
3002 trace_ma_op(__func__, mas); in mas_rebalance()
3013 mas_node_count(mas, empty_count * 2 - 1); in mas_rebalance()
3014 if (mas_is_err(mas)) in mas_rebalance()
3020 mast.bn->type = mte_node_type(mas->node); in mas_rebalance()
3022 l_mas = r_mas = *mas; in mas_rebalance()
3031 mas->offset += shift; in mas_rebalance()
3037 return mas_spanning_rebalance(mas, &mast, empty_count); in mas_rebalance()
3049 static inline void mas_destroy_rebalance(struct ma_state *mas, unsigned char end) in mas_destroy_rebalance() argument
3051 enum maple_type mt = mte_node_type(mas->node); in mas_destroy_rebalance()
3057 bool in_rcu = mt_in_rcu(mas->tree); in mas_destroy_rebalance()
3059 MA_STATE(l_mas, mas->tree, mas->index, mas->last); in mas_destroy_rebalance()
3061 l_mas = *mas; in mas_destroy_rebalance()
3067 mas_node_count(mas, 3); in mas_destroy_rebalance()
3068 if (mas_is_err(mas)) in mas_destroy_rebalance()
3071 newnode = mas_pop_node(mas); in mas_destroy_rebalance()
3076 node = mas_mn(mas); in mas_destroy_rebalance()
3094 mas->min = l_mas.max + 1; in mas_destroy_rebalance()
3125 mas->node = mt_mk_node(newnode, mt); in mas_destroy_rebalance()
3128 new_left = mas_pop_node(mas); in mas_destroy_rebalance()
3139 offset = mte_parent_slot(mas->node); in mas_destroy_rebalance()
3141 parent = mas_pop_node(mas); in mas_destroy_rebalance()
3145 rcu_assign_pointer(slots[offset], mas->node); in mas_destroy_rebalance()
3150 gap = mas_leaf_max_gap(mas); in mas_destroy_rebalance()
3151 mte_set_gap(eparent, mte_parent_slot(mas->node), gap); in mas_destroy_rebalance()
3154 mas_ascend(mas); in mas_destroy_rebalance()
3157 mas_replace_node(mas, old_eparent); in mas_destroy_rebalance()
3158 mas_adopt_children(mas, mas->node); in mas_destroy_rebalance()
3161 mas_update_gap(mas); in mas_destroy_rebalance()
3171 struct ma_state *mas, int height) in mas_split_final_node() argument
3175 if (mte_is_root(mas->node)) { in mas_split_final_node()
3176 if (mt_is_alloc(mas->tree)) in mas_split_final_node()
3180 mas->depth = height; in mas_split_final_node()
3186 ancestor = mas_new_ma_node(mas, mast->bn); in mas_split_final_node()
3187 mas_set_parent(mas, mast->l->node, ancestor, mast->l->offset); in mas_split_final_node()
3188 mas_set_parent(mas, mast->r->node, ancestor, mast->r->offset); in mas_split_final_node()
3189 mte_to_node(ancestor)->parent = mas_mn(mas)->parent; in mas_split_final_node()
3193 mas->offset = mast->bn->b_end - 1; in mas_split_final_node()
3204 struct ma_state *mas, in mast_fill_bnode() argument
3215 if (mte_is_root(mas->node)) { in mast_fill_bnode()
3218 mas_ascend(mas); in mast_fill_bnode()
3219 mas->offset = mte_parent_slot(mas->node); in mast_fill_bnode()
3223 mas_mab_cp(mas, 0, mast->l->offset - 1, mast->bn, 0); in mast_fill_bnode()
3229 if (mast->bn->pivot[mast->bn->b_end - 1] == mas->max) in mast_fill_bnode()
3233 mas_mab_cp(mas, split + skip, mt_slot_count(mas->node) - 1, in mast_fill_bnode()
3237 mast->bn->type = mte_node_type(mas->node); in mast_fill_bnode()
3248 struct ma_state *mas, unsigned char split) in mast_split_data() argument
3255 mast->l->offset = mte_parent_slot(mas->node); in mast_split_data()
3258 if (mte_is_leaf(mas->node)) in mast_split_data()
3280 static inline bool mas_push_data(struct ma_state *mas, int height, in mas_push_data() argument
3286 MA_STATE(tmp_mas, mas->tree, mas->index, mas->last); in mas_push_data()
3287 tmp_mas = *mas; in mas_push_data()
3297 space = 2 * mt_slot_count(mas->node) - 2; in mas_push_data()
3302 if (mas->max == ULONG_MAX) in mas_push_data()
3322 *mas = tmp_mas; in mas_push_data()
3336 mast_split_data(mast, mas, split); in mas_push_data()
3337 mast_fill_bnode(mast, mas, 2); in mas_push_data()
3338 mas_split_final_node(mast, mas, height + 1); in mas_push_data()
3348 static int mas_split(struct ma_state *mas, struct maple_big_node *b_node) in mas_split() argument
3372 MA_STATE(l_mas, mas->tree, mas->index, mas->last); in mas_split()
3373 MA_STATE(r_mas, mas->tree, mas->index, mas->last); in mas_split()
3374 MA_STATE(prev_l_mas, mas->tree, mas->index, mas->last); in mas_split()
3375 MA_STATE(prev_r_mas, mas->tree, mas->index, mas->last); in mas_split()
3377 trace_ma_op(__func__, mas); in mas_split()
3378 mas->depth = mas_mt_height(mas); in mas_split()
3380 mas_node_count(mas, 1 + mas->depth * 2); in mas_split()
3381 if (mas_is_err(mas)) in mas_split()
3390 while (height++ <= mas->depth) { in mas_split()
3392 mas_split_final_node(&mast, mas, height); in mas_split()
3396 l_mas = r_mas = *mas; in mas_split()
3397 l_mas.node = mas_new_ma_node(mas, b_node); in mas_split()
3398 r_mas.node = mas_new_ma_node(mas, b_node); in mas_split()
3407 if (mas_push_data(mas, height, &mast, true)) in mas_split()
3411 if (mas_push_data(mas, height, &mast, false)) in mas_split()
3414 split = mab_calc_split(mas, b_node, &mid_split, prev_l_mas.min); in mas_split()
3415 mast_split_data(&mast, mas, split); in mas_split()
3420 mast.r->max = mas->max; in mas_split()
3421 mast_fill_bnode(&mast, mas, 1); in mas_split()
3427 old = mas->node; in mas_split()
3428 mas->node = l_mas.node; in mas_split()
3429 mas_wmb_replace(mas, old); in mas_split()
3430 mtree_range_walk(mas); in mas_split()
3448 if (mt_in_rcu(wr_mas->mas->tree)) in mas_reuse_node()
3457 mab_mas_cp(bn, 0, bn->b_end, wr_mas->mas, false); in mas_reuse_node()
3475 old_enode = wr_mas->mas->node; in mas_commit_b_node()
3478 (mas_mt_height(wr_mas->mas) > 1)) in mas_commit_b_node()
3479 return mas_rebalance(wr_mas->mas, b_node); in mas_commit_b_node()
3482 return mas_split(wr_mas->mas, b_node); in mas_commit_b_node()
3487 mas_node_count(wr_mas->mas, 1); in mas_commit_b_node()
3488 if (mas_is_err(wr_mas->mas)) in mas_commit_b_node()
3491 node = mas_pop_node(wr_mas->mas); in mas_commit_b_node()
3492 node->parent = mas_mn(wr_mas->mas)->parent; in mas_commit_b_node()
3493 wr_mas->mas->node = mt_mk_node(node, b_type); in mas_commit_b_node()
3494 mab_mas_cp(b_node, 0, b_end, wr_mas->mas, false); in mas_commit_b_node()
3495 mas_replace_node(wr_mas->mas, old_enode); in mas_commit_b_node()
3497 mas_update_gap(wr_mas->mas); in mas_commit_b_node()
3506 static inline int mas_root_expand(struct ma_state *mas, void *entry) in mas_root_expand() argument
3508 void *contents = mas_root_locked(mas); in mas_root_expand()
3515 mas_node_count(mas, 1); in mas_root_expand()
3516 if (unlikely(mas_is_err(mas))) in mas_root_expand()
3519 node = mas_pop_node(mas); in mas_root_expand()
3522 node->parent = ma_parent_ptr(mas_tree_parent(mas)); in mas_root_expand()
3523 mas->node = mt_mk_node(node, type); in mas_root_expand()
3525 if (mas->index) { in mas_root_expand()
3528 if (likely(mas->index > 1)) in mas_root_expand()
3531 pivots[slot++] = mas->index - 1; in mas_root_expand()
3535 mas->offset = slot; in mas_root_expand()
3536 pivots[slot] = mas->last; in mas_root_expand()
3537 if (mas->last != ULONG_MAX) in mas_root_expand()
3540 mas->depth = 1; in mas_root_expand()
3541 mas_set_height(mas); in mas_root_expand()
3544 rcu_assign_pointer(mas->tree->ma_root, mte_mk_root(mas->node)); in mas_root_expand()
3548 static inline void mas_store_root(struct ma_state *mas, void *entry) in mas_store_root() argument
3550 if (likely((mas->last != 0) || (mas->index != 0))) in mas_store_root()
3551 mas_root_expand(mas, entry); in mas_store_root()
3553 mas_root_expand(mas, entry); in mas_store_root()
3555 rcu_assign_pointer(mas->tree->ma_root, entry); in mas_store_root()
3556 mas->node = MAS_START; in mas_store_root()
3576 unsigned long last = wr_mas->mas->last; in mas_is_span_wr()
3585 max = wr_mas->mas->max; in mas_is_span_wr()
3599 trace_ma_write(__func__, wr_mas->mas, wr_mas->r_max, entry); in mas_is_span_wr()
3605 wr_mas->type = mte_node_type(wr_mas->mas->node); in mas_wr_walk_descend()
3612 wr_mas->mas->max = wr_mas->r_max; in mas_wr_walk_traverse()
3613 wr_mas->mas->min = wr_mas->r_min; in mas_wr_walk_traverse()
3614 wr_mas->mas->node = wr_mas->content; in mas_wr_walk_traverse()
3615 wr_mas->mas->offset = 0; in mas_wr_walk_traverse()
3616 wr_mas->mas->depth++; in mas_wr_walk_traverse()
3628 struct ma_state *mas = wr_mas->mas; in mas_wr_walk() local
3635 wr_mas->content = mas_slot_locked(mas, wr_mas->slots, in mas_wr_walk()
3636 mas->offset); in mas_wr_walk()
3648 struct ma_state *mas = wr_mas->mas; in mas_wr_walk_index() local
3652 wr_mas->content = mas_slot_locked(mas, wr_mas->slots, in mas_wr_walk_index()
3653 mas->offset); in mas_wr_walk_index()
3669 struct ma_state *r_mas = r_wr_mas->mas; in mas_extend_spanning_null()
3670 struct ma_state *l_mas = l_wr_mas->mas; in mas_extend_spanning_null()
3701 static inline void *mas_state_walk(struct ma_state *mas) in mas_state_walk() argument
3705 entry = mas_start(mas); in mas_state_walk()
3706 if (mas_is_none(mas)) in mas_state_walk()
3709 if (mas_is_ptr(mas)) in mas_state_walk()
3712 return mtree_range_walk(mas); in mas_state_walk()
3724 static inline void *mtree_lookup_walk(struct ma_state *mas) in mtree_lookup_walk() argument
3735 next = mas->node; in mtree_lookup_walk()
3746 if (pivots[offset] >= mas->index) { in mtree_lookup_walk()
3753 next = mt_slot(mas->tree, slots, offset); in mtree_lookup_walk()
3761 mas_reset(mas); in mtree_lookup_walk()
3776 static inline int mas_new_root(struct ma_state *mas, void *entry) in mas_new_root() argument
3778 struct maple_enode *root = mas_root_locked(mas); in mas_new_root()
3784 if (!entry && !mas->index && mas->last == ULONG_MAX) { in mas_new_root()
3785 mas->depth = 0; in mas_new_root()
3786 mas_set_height(mas); in mas_new_root()
3787 rcu_assign_pointer(mas->tree->ma_root, entry); in mas_new_root()
3788 mas->node = MAS_START; in mas_new_root()
3792 mas_node_count(mas, 1); in mas_new_root()
3793 if (mas_is_err(mas)) in mas_new_root()
3796 node = mas_pop_node(mas); in mas_new_root()
3799 node->parent = ma_parent_ptr(mas_tree_parent(mas)); in mas_new_root()
3800 mas->node = mt_mk_node(node, type); in mas_new_root()
3802 pivots[0] = mas->last; in mas_new_root()
3803 mas->depth = 1; in mas_new_root()
3804 mas_set_height(mas); in mas_new_root()
3805 rcu_assign_pointer(mas->tree->ma_root, mte_mk_root(mas->node)); in mas_new_root()
3809 mte_destroy_walk(root, mas->tree); in mas_new_root()
3826 struct ma_state *mas; in mas_wr_spanning_store() local
3847 mas = wr_mas->mas; in mas_wr_spanning_store()
3848 trace_ma_op(__func__, mas); in mas_wr_spanning_store()
3850 if (unlikely(!mas->index && mas->last == ULONG_MAX)) in mas_wr_spanning_store()
3851 return mas_new_root(mas, wr_mas->entry); in mas_wr_spanning_store()
3856 height = mas_mt_height(mas); in mas_wr_spanning_store()
3857 mas_node_count(mas, 1 + height * 3); in mas_wr_spanning_store()
3858 if (mas_is_err(mas)) in mas_wr_spanning_store()
3866 r_mas = *mas; in mas_wr_spanning_store()
3873 r_mas.last = r_mas.index = mas->last; in mas_wr_spanning_store()
3876 l_mas = *mas; in mas_wr_spanning_store()
3881 mas->offset = l_mas.offset; in mas_wr_spanning_store()
3882 mas->index = l_mas.index; in mas_wr_spanning_store()
3883 mas->last = l_mas.last = r_mas.last; in mas_wr_spanning_store()
3888 mas_set_range(mas, 0, ULONG_MAX); in mas_wr_spanning_store()
3889 return mas_new_root(mas, wr_mas->entry); in mas_wr_spanning_store()
3903 l_mas.index = l_mas.last = mas->index; in mas_wr_spanning_store()
3909 return mas_spanning_rebalance(mas, &mast, height + 1); in mas_wr_spanning_store()
3923 struct ma_state *mas = wr_mas->mas; in mas_wr_node_store() local
3929 bool in_rcu = mt_in_rcu(mas->tree); in mas_wr_node_store()
3932 if (!mte_is_root(mas->node) && (new_end <= mt_min_slots[wr_mas->type]) && in mas_wr_node_store()
3933 !(mas->mas_flags & MA_STATE_BULK)) in mas_wr_node_store()
3936 if (mas->last == wr_mas->end_piv) in mas_wr_node_store()
3939 mas_bulk_rebalance(mas, wr_mas->node_end, wr_mas->type); in mas_wr_node_store()
3943 mas_node_count(mas, 1); in mas_wr_node_store()
3944 if (mas_is_err(mas)) in mas_wr_node_store()
3947 newnode = mas_pop_node(mas); in mas_wr_node_store()
3953 newnode->parent = mas_mn(mas)->parent; in mas_wr_node_store()
3957 memcpy(dst_pivots, wr_mas->pivots, sizeof(unsigned long) * mas->offset); in mas_wr_node_store()
3958 memcpy(dst_slots, wr_mas->slots, sizeof(void *) * mas->offset); in mas_wr_node_store()
3961 if (wr_mas->r_min < mas->index) { in mas_wr_node_store()
3962 rcu_assign_pointer(dst_slots[mas->offset], wr_mas->content); in mas_wr_node_store()
3963 dst_pivots[mas->offset++] = mas->index - 1; in mas_wr_node_store()
3967 if (mas->offset < node_pivots) in mas_wr_node_store()
3968 dst_pivots[mas->offset] = mas->last; in mas_wr_node_store()
3969 rcu_assign_pointer(dst_slots[mas->offset], wr_mas->entry); in mas_wr_node_store()
3978 dst_offset = mas->offset + 1; in mas_wr_node_store()
3987 dst_pivots[new_end] = mas->max; in mas_wr_node_store()
3990 mas_leaf_set_meta(mas, newnode, dst_pivots, maple_leaf_64, new_end); in mas_wr_node_store()
3992 struct maple_enode *old_enode = mas->node; in mas_wr_node_store()
3994 mas->node = mt_mk_node(newnode, wr_mas->type); in mas_wr_node_store()
3995 mas_replace_node(mas, old_enode); in mas_wr_node_store()
3999 trace_ma_write(__func__, mas, 0, wr_mas->entry); in mas_wr_node_store()
4000 mas_update_gap(mas); in mas_wr_node_store()
4012 struct ma_state *mas = wr_mas->mas; in mas_wr_slot_store() local
4013 unsigned char offset = mas->offset; in mas_wr_slot_store()
4017 gap |= !mt_slot_locked(mas->tree, slots, offset); in mas_wr_slot_store()
4018 gap |= !mt_slot_locked(mas->tree, slots, offset + 1); in mas_wr_slot_store()
4021 if (mas->index == wr_mas->r_min) { in mas_wr_slot_store()
4024 wr_mas->pivots[offset] = mas->last; in mas_wr_slot_store()
4028 wr_mas->pivots[offset] = mas->index - 1; in mas_wr_slot_store()
4029 mas->offset++; /* Keep mas accurate. */ in mas_wr_slot_store()
4031 } else if (!mt_in_rcu(mas->tree)) { in mas_wr_slot_store()
4036 gap |= !mt_slot_locked(mas->tree, slots, offset + 2); in mas_wr_slot_store()
4038 wr_mas->pivots[offset] = mas->index - 1; in mas_wr_slot_store()
4039 wr_mas->pivots[offset + 1] = mas->last; in mas_wr_slot_store()
4040 mas->offset++; /* Keep mas accurate. */ in mas_wr_slot_store()
4045 trace_ma_write(__func__, mas, 0, wr_mas->entry); in mas_wr_slot_store()
4051 mas_update_gap(mas); in mas_wr_slot_store()
4058 struct ma_state *mas = wr_mas->mas; in mas_wr_extend_null() local
4062 mas->last = wr_mas->end_piv; in mas_wr_extend_null()
4065 if ((mas->last == wr_mas->end_piv) && in mas_wr_extend_null()
4070 mas->last = mas->max; in mas_wr_extend_null()
4072 mas->last = wr_mas->pivots[wr_mas->offset_end]; in mas_wr_extend_null()
4073 wr_mas->end_piv = mas->last; in mas_wr_extend_null()
4079 mas->index = wr_mas->r_min; in mas_wr_extend_null()
4082 if (mas->index == wr_mas->r_min && mas->offset && in mas_wr_extend_null()
4083 !wr_mas->slots[mas->offset - 1]) { in mas_wr_extend_null()
4084 mas->offset--; in mas_wr_extend_null()
4085 wr_mas->r_min = mas->index = in mas_wr_extend_null()
4086 mas_safe_min(mas, wr_mas->pivots, mas->offset); in mas_wr_extend_null()
4087 wr_mas->r_max = wr_mas->pivots[mas->offset]; in mas_wr_extend_null()
4095 (wr_mas->mas->last > wr_mas->pivots[wr_mas->offset_end])) in mas_wr_end_piv()
4101 wr_mas->end_piv = wr_mas->mas->max; in mas_wr_end_piv()
4109 struct ma_state *mas = wr_mas->mas; in mas_wr_new_end() local
4112 new_end -= wr_mas->offset_end - mas->offset; in mas_wr_new_end()
4113 if (wr_mas->r_min == mas->index) in mas_wr_new_end()
4116 if (wr_mas->end_piv == mas->last) in mas_wr_new_end()
4136 struct ma_state *mas; in mas_wr_append() local
4140 mas = wr_mas->mas; in mas_wr_append()
4141 if (mt_in_rcu(mas->tree)) in mas_wr_append()
4144 if (mas->offset != wr_mas->node_end) in mas_wr_append()
4148 if (mas->offset != end) in mas_wr_append()
4158 if (mas->last == wr_mas->r_max) { in mas_wr_append()
4161 wr_mas->pivots[end] = mas->index - 1; in mas_wr_append()
4162 mas->offset = new_end; in mas_wr_append()
4166 wr_mas->pivots[end] = mas->last; in mas_wr_append()
4172 wr_mas->pivots[end + 1] = mas->last; in mas_wr_append()
4174 wr_mas->pivots[end] = mas->index - 1; in mas_wr_append()
4175 mas->offset = end + 1; in mas_wr_append()
4179 mas_update_gap(mas); in mas_wr_append()
4181 trace_ma_write(__func__, mas, new_end, wr_mas->entry); in mas_wr_append()
4195 trace_ma_write(__func__, wr_mas->mas, 0, wr_mas->entry); in mas_wr_bnode()
4203 struct ma_state *mas = wr_mas->mas; in mas_wr_modify() local
4207 if (wr_mas->r_min == mas->index && wr_mas->r_max == mas->last) { in mas_wr_modify()
4208 rcu_assign_pointer(wr_mas->slots[mas->offset], wr_mas->entry); in mas_wr_modify()
4210 mas_update_gap(mas); in mas_wr_modify()
4232 if (mas_is_err(mas)) in mas_wr_modify()
4248 struct ma_state *mas = wr_mas->mas; in mas_wr_store_entry() local
4250 wr_mas->content = mas_start(mas); in mas_wr_store_entry()
4251 if (mas_is_none(mas) || mas_is_ptr(mas)) { in mas_wr_store_entry()
4252 mas_store_root(mas, wr_mas->entry); in mas_wr_store_entry()
4264 if (unlikely(!mas->index && mas->last == ULONG_MAX)) { in mas_wr_store_entry()
4265 mas_new_root(mas, wr_mas->entry); in mas_wr_store_entry()
4281 static inline void *mas_insert(struct ma_state *mas, void *entry) in mas_insert() argument
4283 MA_WR_STATE(wr_mas, mas, entry); in mas_insert()
4299 wr_mas.content = mas_start(mas); in mas_insert()
4303 if (mas_is_none(mas) || mas_is_ptr(mas)) { in mas_insert()
4304 mas_store_root(mas, entry); in mas_insert()
4313 wr_mas.offset_end = mas->offset; in mas_insert()
4316 if (wr_mas.content || (mas->last > wr_mas.r_max)) in mas_insert()
4326 mas_set_err(mas, -EEXIST); in mas_insert()
4331 static inline void mas_rewalk(struct ma_state *mas, unsigned long index) in mas_rewalk() argument
4334 mas_set(mas, index); in mas_rewalk()
4335 mas_state_walk(mas); in mas_rewalk()
4336 if (mas_is_start(mas)) in mas_rewalk()
4340 static inline bool mas_rewalk_if_dead(struct ma_state *mas, in mas_rewalk_if_dead() argument
4344 mas_rewalk(mas, index); in mas_rewalk_if_dead()
4359 static inline int mas_prev_node(struct ma_state *mas, unsigned long min) in mas_prev_node() argument
4368 node = mas_mn(mas); in mas_prev_node()
4369 if (!mas->min) in mas_prev_node()
4372 max = mas->min - 1; in mas_prev_node()
4382 if (unlikely(mas_ascend(mas))) in mas_prev_node()
4384 offset = mas->offset; in mas_prev_node()
4386 node = mas_mn(mas); in mas_prev_node()
4390 mt = mte_node_type(mas->node); in mas_prev_node()
4394 mas->node = mas_slot(mas, slots, offset); in mas_prev_node()
4398 mt = mte_node_type(mas->node); in mas_prev_node()
4399 node = mas_mn(mas); in mas_prev_node()
4407 mas->node = mas_slot(mas, slots, offset); in mas_prev_node()
4413 mas->min = pivots[offset - 1] + 1; in mas_prev_node()
4414 mas->max = max; in mas_prev_node()
4415 mas->offset = mas_data_end(mas); in mas_prev_node()
4416 if (unlikely(mte_dead_node(mas->node))) in mas_prev_node()
4425 mas->node = MAS_NONE; in mas_prev_node()
4439 static void *mas_prev_slot(struct ma_state *mas, unsigned long min, bool empty, in mas_prev_slot() argument
4448 unsigned long save_point = mas->index; in mas_prev_slot()
4451 node = mas_mn(mas); in mas_prev_slot()
4452 type = mte_node_type(mas->node); in mas_prev_slot()
4454 if (unlikely(mas_rewalk_if_dead(mas, node, save_point))) in mas_prev_slot()
4457 if (mas->min <= min) { in mas_prev_slot()
4458 pivot = mas_safe_min(mas, pivots, mas->offset); in mas_prev_slot()
4460 if (unlikely(mas_rewalk_if_dead(mas, node, save_point))) in mas_prev_slot()
4468 if (likely(mas->offset)) { in mas_prev_slot()
4469 mas->offset--; in mas_prev_slot()
4470 mas->last = mas->index - 1; in mas_prev_slot()
4471 mas->index = mas_safe_min(mas, pivots, mas->offset); in mas_prev_slot()
4473 if (mas_prev_node(mas, min)) { in mas_prev_slot()
4474 mas_rewalk(mas, save_point); in mas_prev_slot()
4478 if (mas_is_none(mas)) in mas_prev_slot()
4481 mas->last = mas->max; in mas_prev_slot()
4482 node = mas_mn(mas); in mas_prev_slot()
4483 type = mte_node_type(mas->node); in mas_prev_slot()
4485 mas->index = pivots[mas->offset - 1] + 1; in mas_prev_slot()
4489 entry = mas_slot(mas, slots, mas->offset); in mas_prev_slot()
4490 if (unlikely(mas_rewalk_if_dead(mas, node, save_point))) in mas_prev_slot()
4497 if (mas->index <= min) in mas_prev_slot()
4507 mas->node = MAS_UNDERFLOW; in mas_prev_slot()
4519 static inline int mas_next_node(struct ma_state *mas, struct maple_node *node, in mas_next_node() argument
4530 if (mas->max >= max) in mas_next_node()
4533 min = mas->max + 1; in mas_next_node()
4540 if (unlikely(mas_ascend(mas))) in mas_next_node()
4544 node = mas_mn(mas); in mas_next_node()
4545 mt = mte_node_type(mas->node); in mas_next_node()
4547 node_end = ma_data_end(node, mt, pivots, mas->max); in mas_next_node()
4551 } while (unlikely(mas->offset == node_end)); in mas_next_node()
4554 mas->offset++; in mas_next_node()
4555 enode = mas_slot(mas, slots, mas->offset); in mas_next_node()
4560 mas->offset = 0; in mas_next_node()
4564 mas->node = enode; in mas_next_node()
4565 node = mas_mn(mas); in mas_next_node()
4566 mt = mte_node_type(mas->node); in mas_next_node()
4568 enode = mas_slot(mas, slots, 0); in mas_next_node()
4573 if (!mas->offset) in mas_next_node()
4576 mas->max = mas_safe_pivot(mas, pivots, mas->offset, mt); in mas_next_node()
4580 mas->node = enode; in mas_next_node()
4581 mas->min = min; in mas_next_node()
4588 mas->node = MAS_NONE; in mas_next_node()
4603 static void *mas_next_slot(struct ma_state *mas, unsigned long max, bool empty, in mas_next_slot() argument
4612 unsigned long save_point = mas->last; in mas_next_slot()
4616 node = mas_mn(mas); in mas_next_slot()
4617 type = mte_node_type(mas->node); in mas_next_slot()
4619 data_end = ma_data_end(node, type, pivots, mas->max); in mas_next_slot()
4620 if (unlikely(mas_rewalk_if_dead(mas, node, save_point))) in mas_next_slot()
4623 if (mas->max >= max) { in mas_next_slot()
4624 if (likely(mas->offset < data_end)) in mas_next_slot()
4625 pivot = pivots[mas->offset]; in mas_next_slot()
4629 if (unlikely(mas_rewalk_if_dead(mas, node, save_point))) in mas_next_slot()
4636 if (likely(mas->offset < data_end)) { in mas_next_slot()
4637 mas->index = pivots[mas->offset] + 1; in mas_next_slot()
4639 mas->offset++; in mas_next_slot()
4640 if (likely(mas->offset < data_end)) in mas_next_slot()
4641 mas->last = pivots[mas->offset]; in mas_next_slot()
4643 mas->last = mas->max; in mas_next_slot()
4645 if (mas_next_node(mas, node, max)) { in mas_next_slot()
4646 mas_rewalk(mas, save_point); in mas_next_slot()
4650 if (WARN_ON_ONCE(mas_is_none(mas))) { in mas_next_slot()
4651 mas->node = MAS_OVERFLOW; in mas_next_slot()
4656 mas->offset = 0; in mas_next_slot()
4657 mas->index = mas->min; in mas_next_slot()
4658 node = mas_mn(mas); in mas_next_slot()
4659 type = mte_node_type(mas->node); in mas_next_slot()
4661 mas->last = pivots[0]; in mas_next_slot()
4665 entry = mt_slot(mas->tree, slots, mas->offset); in mas_next_slot()
4666 if (unlikely(mas_rewalk_if_dead(mas, node, save_point))) in mas_next_slot()
4673 if (mas->last >= max) in mas_next_slot()
4676 mas->index = mas->last + 1; in mas_next_slot()
4685 mas->node = MAS_OVERFLOW; in mas_next_slot()
4702 static inline void *mas_next_entry(struct ma_state *mas, unsigned long limit) in mas_next_entry() argument
4704 if (mas->last >= limit) { in mas_next_entry()
4705 mas->node = MAS_OVERFLOW; in mas_next_entry()
4709 return mas_next_slot(mas, limit, false, true); in mas_next_entry()
4721 static bool mas_rev_awalk(struct ma_state *mas, unsigned long size, in mas_rev_awalk() argument
4724 enum maple_type type = mte_node_type(mas->node); in mas_rev_awalk()
4725 struct maple_node *node = mas_mn(mas); in mas_rev_awalk()
4732 if (unlikely(mas_is_err(mas))) in mas_rev_awalk()
4737 mas->offset = (unsigned char)(mas->index - mas->min); in mas_rev_awalk()
4744 offset = mas->offset; in mas_rev_awalk()
4745 min = mas_safe_min(mas, pivots, offset); in mas_rev_awalk()
4747 while (mas->last < min) in mas_rev_awalk()
4748 min = mas_safe_min(mas, pivots, --offset); in mas_rev_awalk()
4750 max = mas_safe_pivot(mas, pivots, offset, type); in mas_rev_awalk()
4751 while (mas->index <= max) { in mas_rev_awalk()
4755 else if (!mas_slot(mas, slots, offset)) in mas_rev_awalk()
4759 if ((size <= gap) && (size <= mas->last - min + 1)) in mas_rev_awalk()
4769 min = mas_safe_min(mas, pivots, offset); in mas_rev_awalk()
4779 min = mas_safe_min(mas, pivots, offset); in mas_rev_awalk()
4782 if (unlikely((mas->index > max) || (size - 1 > max - mas->index))) in mas_rev_awalk()
4786 mas->offset = offset; in mas_rev_awalk()
4793 mas->node = mas_slot(mas, slots, offset); in mas_rev_awalk()
4794 mas->min = min; in mas_rev_awalk()
4795 mas->max = max; in mas_rev_awalk()
4796 mas->offset = mas_data_end(mas); in mas_rev_awalk()
4800 if (!mte_is_root(mas->node)) in mas_rev_awalk()
4804 mas_set_err(mas, -EBUSY); in mas_rev_awalk()
4808 static inline bool mas_anode_descend(struct ma_state *mas, unsigned long size) in mas_anode_descend() argument
4810 enum maple_type type = mte_node_type(mas->node); in mas_anode_descend()
4819 mas->offset = (unsigned char)(mas->index - mas->min); in mas_anode_descend()
4823 node = mas_mn(mas); in mas_anode_descend()
4827 offset = mas->offset; in mas_anode_descend()
4828 min = mas_safe_min(mas, pivots, offset); in mas_anode_descend()
4829 data_end = ma_data_end(node, type, pivots, mas->max); in mas_anode_descend()
4831 pivot = mas_safe_pivot(mas, pivots, offset, type); in mas_anode_descend()
4834 if (mas->index > pivot) in mas_anode_descend()
4839 else if (!mas_slot(mas, slots, offset)) in mas_anode_descend()
4840 gap = min(pivot, mas->last) - max(mas->index, min) + 1; in mas_anode_descend()
4849 if (mas->index <= pivot) { in mas_anode_descend()
4850 mas->node = mas_slot(mas, slots, offset); in mas_anode_descend()
4851 mas->min = min; in mas_anode_descend()
4852 mas->max = pivot; in mas_anode_descend()
4859 if (mas->last <= pivot) { in mas_anode_descend()
4860 mas_set_err(mas, -EBUSY); in mas_anode_descend()
4865 if (mte_is_root(mas->node)) in mas_anode_descend()
4868 mas->offset = offset; in mas_anode_descend()
4881 void *mas_walk(struct ma_state *mas) in mas_walk() argument
4885 if (!mas_is_active(mas) || !mas_is_start(mas)) in mas_walk()
4886 mas->node = MAS_START; in mas_walk()
4888 entry = mas_state_walk(mas); in mas_walk()
4889 if (mas_is_start(mas)) { in mas_walk()
4891 } else if (mas_is_none(mas)) { in mas_walk()
4892 mas->index = 0; in mas_walk()
4893 mas->last = ULONG_MAX; in mas_walk()
4894 } else if (mas_is_ptr(mas)) { in mas_walk()
4895 if (!mas->index) { in mas_walk()
4896 mas->last = 0; in mas_walk()
4900 mas->index = 1; in mas_walk()
4901 mas->last = ULONG_MAX; in mas_walk()
4902 mas->node = MAS_NONE; in mas_walk()
4910 static inline bool mas_rewind_node(struct ma_state *mas) in mas_rewind_node() argument
4915 if (mte_is_root(mas->node)) { in mas_rewind_node()
4916 slot = mas->offset; in mas_rewind_node()
4920 mas_ascend(mas); in mas_rewind_node()
4921 slot = mas->offset; in mas_rewind_node()
4925 mas->offset = --slot; in mas_rewind_node()
4935 static inline bool mas_skip_node(struct ma_state *mas) in mas_skip_node() argument
4937 if (mas_is_err(mas)) in mas_skip_node()
4941 if (mte_is_root(mas->node)) { in mas_skip_node()
4942 if (mas->offset >= mas_data_end(mas)) { in mas_skip_node()
4943 mas_set_err(mas, -EBUSY); in mas_skip_node()
4947 mas_ascend(mas); in mas_skip_node()
4949 } while (mas->offset >= mas_data_end(mas)); in mas_skip_node()
4951 mas->offset++; in mas_skip_node()
4963 static inline void mas_awalk(struct ma_state *mas, unsigned long size) in mas_awalk() argument
4974 while (!mas_is_err(mas) && !mas_anode_descend(mas, size)) { in mas_awalk()
4975 if (last == mas->node) in mas_awalk()
4976 mas_skip_node(mas); in mas_awalk()
4978 last = mas->node; in mas_awalk()
4991 static inline int mas_sparse_area(struct ma_state *mas, unsigned long min, in mas_sparse_area() argument
4994 if (!unlikely(mas_is_none(mas)) && min == 0) { in mas_sparse_area()
5006 mas->index = min; in mas_sparse_area()
5007 mas->last = min + size - 1; in mas_sparse_area()
5009 mas->last = max; in mas_sparse_area()
5010 mas->index = max - size + 1; in mas_sparse_area()
5023 int mas_empty_area(struct ma_state *mas, unsigned long min, in mas_empty_area() argument
5036 if (mas_is_start(mas)) in mas_empty_area()
5037 mas_start(mas); in mas_empty_area()
5038 else if (mas->offset >= 2) in mas_empty_area()
5039 mas->offset -= 2; in mas_empty_area()
5040 else if (!mas_skip_node(mas)) in mas_empty_area()
5044 if (mas_is_none(mas) || mas_is_ptr(mas)) in mas_empty_area()
5045 return mas_sparse_area(mas, min, max, size, true); in mas_empty_area()
5048 mas->index = min; in mas_empty_area()
5049 mas->last = max; in mas_empty_area()
5050 mas_awalk(mas, size); in mas_empty_area()
5052 if (unlikely(mas_is_err(mas))) in mas_empty_area()
5053 return xa_err(mas->node); in mas_empty_area()
5055 offset = mas->offset; in mas_empty_area()
5059 mt = mte_node_type(mas->node); in mas_empty_area()
5060 pivots = ma_pivots(mas_mn(mas), mt); in mas_empty_area()
5061 min = mas_safe_min(mas, pivots, offset); in mas_empty_area()
5062 if (mas->index < min) in mas_empty_area()
5063 mas->index = min; in mas_empty_area()
5064 mas->last = mas->index + size - 1; in mas_empty_area()
5077 int mas_empty_area_rev(struct ma_state *mas, unsigned long min, in mas_empty_area_rev() argument
5080 struct maple_enode *last = mas->node; in mas_empty_area_rev()
5088 if (mas_is_start(mas)) { in mas_empty_area_rev()
5089 mas_start(mas); in mas_empty_area_rev()
5090 mas->offset = mas_data_end(mas); in mas_empty_area_rev()
5091 } else if (mas->offset >= 2) { in mas_empty_area_rev()
5092 mas->offset -= 2; in mas_empty_area_rev()
5093 } else if (!mas_rewind_node(mas)) { in mas_empty_area_rev()
5098 if (mas_is_none(mas) || mas_is_ptr(mas)) in mas_empty_area_rev()
5099 return mas_sparse_area(mas, min, max, size, false); in mas_empty_area_rev()
5102 mas->index = min; in mas_empty_area_rev()
5103 mas->last = max; in mas_empty_area_rev()
5105 while (!mas_rev_awalk(mas, size, &min, &max)) { in mas_empty_area_rev()
5106 if (last == mas->node) { in mas_empty_area_rev()
5107 if (!mas_rewind_node(mas)) in mas_empty_area_rev()
5110 last = mas->node; in mas_empty_area_rev()
5114 if (mas_is_err(mas)) in mas_empty_area_rev()
5115 return xa_err(mas->node); in mas_empty_area_rev()
5117 if (unlikely(mas->offset == MAPLE_NODE_SLOTS)) in mas_empty_area_rev()
5121 if (max < mas->last) in mas_empty_area_rev()
5122 mas->last = max; in mas_empty_area_rev()
5124 mas->index = mas->last - size + 1; in mas_empty_area_rev()
5342 if (!mas_is_active(wr_mas->mas)) { in mas_wr_store_setup()
5343 if (mas_is_start(wr_mas->mas)) in mas_wr_store_setup()
5346 if (unlikely(mas_is_paused(wr_mas->mas))) in mas_wr_store_setup()
5349 if (unlikely(mas_is_none(wr_mas->mas))) in mas_wr_store_setup()
5352 if (unlikely(mas_is_overflow(wr_mas->mas))) in mas_wr_store_setup()
5355 if (unlikely(mas_is_underflow(wr_mas->mas))) in mas_wr_store_setup()
5364 if (wr_mas->mas->last > wr_mas->mas->max) in mas_wr_store_setup()
5370 if (mte_is_leaf(wr_mas->mas->node) && in mas_wr_store_setup()
5371 wr_mas->mas->last == wr_mas->mas->max) in mas_wr_store_setup()
5377 mas_reset(wr_mas->mas); in mas_wr_store_setup()
5393 void *mas_store(struct ma_state *mas, void *entry) in mas_store() argument
5395 MA_WR_STATE(wr_mas, mas, entry); in mas_store()
5397 trace_ma_write(__func__, mas, 0, entry); in mas_store()
5399 if (MAS_WARN_ON(mas, mas->index > mas->last)) in mas_store()
5400 pr_err("Error %lX > %lX %p\n", mas->index, mas->last, entry); in mas_store()
5402 if (mas->index > mas->last) { in mas_store()
5403 mas_set_err(mas, -EINVAL); in mas_store()
5430 int mas_store_gfp(struct ma_state *mas, void *entry, gfp_t gfp) in mas_store_gfp() argument
5432 MA_WR_STATE(wr_mas, mas, entry); in mas_store_gfp()
5435 trace_ma_write(__func__, mas, 0, entry); in mas_store_gfp()
5438 if (unlikely(mas_nomem(mas, gfp))) in mas_store_gfp()
5441 if (unlikely(mas_is_err(mas))) in mas_store_gfp()
5442 return xa_err(mas->node); in mas_store_gfp()
5454 void mas_store_prealloc(struct ma_state *mas, void *entry) in mas_store_prealloc() argument
5456 MA_WR_STATE(wr_mas, mas, entry); in mas_store_prealloc()
5459 trace_ma_write(__func__, mas, 0, entry); in mas_store_prealloc()
5461 MAS_WR_BUG_ON(&wr_mas, mas_is_err(mas)); in mas_store_prealloc()
5462 mas_destroy(mas); in mas_store_prealloc()
5474 int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp) in mas_preallocate() argument
5476 MA_WR_STATE(wr_mas, mas, entry); in mas_preallocate()
5482 if (unlikely(!mas->index && mas->last == ULONG_MAX)) in mas_preallocate()
5486 wr_mas.content = mas_start(mas); in mas_preallocate()
5488 if (unlikely(mas_is_none(mas) || mas_is_ptr(mas))) in mas_preallocate()
5493 request = 1 + mas_mt_height(mas) * 3; in mas_preallocate()
5499 if (wr_mas.r_min == mas->index && wr_mas.r_max == mas->last) in mas_preallocate()
5506 request = 1 + mas_mt_height(mas) * 2; in mas_preallocate()
5511 if (unlikely(mte_is_root(mas->node))) in mas_preallocate()
5516 request = mas_mt_height(mas) * 2 - 1; in mas_preallocate()
5520 mas_node_count_gfp(mas, request, gfp); in mas_preallocate()
5521 mas->mas_flags |= MA_STATE_PREALLOC; in mas_preallocate()
5522 if (likely(!mas_is_err(mas))) in mas_preallocate()
5525 mas_set_alloc_req(mas, 0); in mas_preallocate()
5526 ret = xa_err(mas->node); in mas_preallocate()
5527 mas_reset(mas); in mas_preallocate()
5528 mas_destroy(mas); in mas_preallocate()
5529 mas_reset(mas); in mas_preallocate()
5542 void mas_destroy(struct ma_state *mas) in mas_destroy() argument
5553 if (mas->mas_flags & MA_STATE_REBALANCE) { in mas_destroy()
5556 mas_start(mas); in mas_destroy()
5557 mtree_range_walk(mas); in mas_destroy()
5558 end = mas_data_end(mas) + 1; in mas_destroy()
5559 if (end < mt_min_slot_count(mas->node) - 1) in mas_destroy()
5560 mas_destroy_rebalance(mas, end); in mas_destroy()
5562 mas->mas_flags &= ~MA_STATE_REBALANCE; in mas_destroy()
5564 mas->mas_flags &= ~(MA_STATE_BULK|MA_STATE_PREALLOC); in mas_destroy()
5566 total = mas_allocated(mas); in mas_destroy()
5568 node = mas->alloc; in mas_destroy()
5569 mas->alloc = node->slot[0]; in mas_destroy()
5580 mas->alloc = NULL; in mas_destroy()
5596 int mas_expected_entries(struct ma_state *mas, unsigned long nr_entries) in mas_expected_entries() argument
5599 struct maple_enode *enode = mas->node; in mas_expected_entries()
5614 mas->mas_flags |= MA_STATE_BULK; in mas_expected_entries()
5622 if (!mt_is_alloc(mas->tree)) in mas_expected_entries()
5630 mas_node_count_gfp(mas, nr_nodes + 3, GFP_KERNEL); in mas_expected_entries()
5633 mas->mas_flags |= MA_STATE_PREALLOC; in mas_expected_entries()
5635 if (!mas_is_err(mas)) in mas_expected_entries()
5638 ret = xa_err(mas->node); in mas_expected_entries()
5639 mas->node = enode; in mas_expected_entries()
5640 mas_destroy(mas); in mas_expected_entries()
5646 static inline bool mas_next_setup(struct ma_state *mas, unsigned long max, in mas_next_setup() argument
5649 bool was_none = mas_is_none(mas); in mas_next_setup()
5651 if (unlikely(mas->last >= max)) { in mas_next_setup()
5652 mas->node = MAS_OVERFLOW; in mas_next_setup()
5656 if (mas_is_active(mas)) in mas_next_setup()
5659 if (mas_is_none(mas) || mas_is_paused(mas)) { in mas_next_setup()
5660 mas->node = MAS_START; in mas_next_setup()
5661 } else if (mas_is_overflow(mas)) { in mas_next_setup()
5663 mas->node = MAS_START; in mas_next_setup()
5664 } else if (mas_is_underflow(mas)) { in mas_next_setup()
5665 mas->node = MAS_START; in mas_next_setup()
5666 *entry = mas_walk(mas); in mas_next_setup()
5671 if (mas_is_start(mas)) in mas_next_setup()
5672 *entry = mas_walk(mas); /* Retries on dead nodes handled by mas_walk */ in mas_next_setup()
5674 if (mas_is_ptr(mas)) { in mas_next_setup()
5676 if (was_none && mas->index == 0) { in mas_next_setup()
5677 mas->index = mas->last = 0; in mas_next_setup()
5680 mas->index = 1; in mas_next_setup()
5681 mas->last = ULONG_MAX; in mas_next_setup()
5682 mas->node = MAS_NONE; in mas_next_setup()
5686 if (mas_is_none(mas)) in mas_next_setup()
5703 void *mas_next(struct ma_state *mas, unsigned long max) in mas_next() argument
5707 if (mas_next_setup(mas, max, &entry)) in mas_next()
5711 return mas_next_slot(mas, max, false, true); in mas_next()
5726 void *mas_next_range(struct ma_state *mas, unsigned long max) in mas_next_range() argument
5730 if (mas_next_setup(mas, max, &entry)) in mas_next_range()
5734 return mas_next_slot(mas, max, true, true); in mas_next_range()
5753 MA_STATE(mas, mt, index, index); in mt_next()
5756 entry = mas_next(&mas, max); in mt_next()
5762 static inline bool mas_prev_setup(struct ma_state *mas, unsigned long min, in mas_prev_setup() argument
5765 if (unlikely(mas->index <= min)) { in mas_prev_setup()
5766 mas->node = MAS_UNDERFLOW; in mas_prev_setup()
5770 if (mas_is_active(mas)) in mas_prev_setup()
5773 if (mas_is_overflow(mas)) { in mas_prev_setup()
5774 mas->node = MAS_START; in mas_prev_setup()
5775 *entry = mas_walk(mas); in mas_prev_setup()
5780 if (mas_is_none(mas) || mas_is_paused(mas)) { in mas_prev_setup()
5781 mas->node = MAS_START; in mas_prev_setup()
5782 } else if (mas_is_underflow(mas)) { in mas_prev_setup()
5784 mas->node = MAS_START; in mas_prev_setup()
5787 if (mas_is_start(mas)) in mas_prev_setup()
5788 mas_walk(mas); in mas_prev_setup()
5790 if (unlikely(mas_is_ptr(mas))) { in mas_prev_setup()
5791 if (!mas->index) in mas_prev_setup()
5793 mas->index = mas->last = 0; in mas_prev_setup()
5794 *entry = mas_root(mas); in mas_prev_setup()
5798 if (mas_is_none(mas)) { in mas_prev_setup()
5799 if (mas->index) { in mas_prev_setup()
5801 mas->index = mas->last = 0; in mas_prev_setup()
5802 mas->node = MAS_ROOT; in mas_prev_setup()
5803 *entry = mas_root(mas); in mas_prev_setup()
5812 mas->node = MAS_NONE; in mas_prev_setup()
5827 void *mas_prev(struct ma_state *mas, unsigned long min) in mas_prev() argument
5831 if (mas_prev_setup(mas, min, &entry)) in mas_prev()
5834 return mas_prev_slot(mas, min, false, true); in mas_prev()
5850 void *mas_prev_range(struct ma_state *mas, unsigned long min) in mas_prev_range() argument
5854 if (mas_prev_setup(mas, min, &entry)) in mas_prev_range()
5857 return mas_prev_slot(mas, min, true, true); in mas_prev_range()
5876 MA_STATE(mas, mt, index, index); in mt_prev()
5879 entry = mas_prev(&mas, min); in mt_prev()
5898 void mas_pause(struct ma_state *mas) in mas_pause() argument
5900 mas->node = MAS_PAUSE; in mas_pause()
5912 static inline bool mas_find_setup(struct ma_state *mas, unsigned long max, in mas_find_setup() argument
5915 if (mas_is_active(mas)) { in mas_find_setup()
5916 if (mas->last < max) in mas_find_setup()
5922 if (mas_is_paused(mas)) { in mas_find_setup()
5923 if (unlikely(mas->last >= max)) in mas_find_setup()
5926 mas->index = ++mas->last; in mas_find_setup()
5927 mas->node = MAS_START; in mas_find_setup()
5928 } else if (mas_is_none(mas)) { in mas_find_setup()
5929 if (unlikely(mas->last >= max)) in mas_find_setup()
5932 mas->index = mas->last; in mas_find_setup()
5933 mas->node = MAS_START; in mas_find_setup()
5934 } else if (mas_is_overflow(mas) || mas_is_underflow(mas)) { in mas_find_setup()
5935 if (mas->index > max) { in mas_find_setup()
5936 mas->node = MAS_OVERFLOW; in mas_find_setup()
5940 mas->node = MAS_START; in mas_find_setup()
5943 if (mas_is_start(mas)) { in mas_find_setup()
5945 if (mas->index > max) in mas_find_setup()
5948 *entry = mas_walk(mas); in mas_find_setup()
5954 if (unlikely(!mas_searchable(mas))) { in mas_find_setup()
5955 if (unlikely(mas_is_ptr(mas))) in mas_find_setup()
5961 if (mas->index == max) in mas_find_setup()
5967 mas->node = MAS_NONE; in mas_find_setup()
5968 mas->index = 1; in mas_find_setup()
5969 mas->last = ULONG_MAX; in mas_find_setup()
5985 void *mas_find(struct ma_state *mas, unsigned long max) in mas_find() argument
5989 if (mas_find_setup(mas, max, &entry)) in mas_find()
5993 return mas_next_slot(mas, max, false, false); in mas_find()
6009 void *mas_find_range(struct ma_state *mas, unsigned long max) in mas_find_range() argument
6013 if (mas_find_setup(mas, max, &entry)) in mas_find_range()
6017 return mas_next_slot(mas, max, true, false); in mas_find_range()
6029 static inline bool mas_find_rev_setup(struct ma_state *mas, unsigned long min, in mas_find_rev_setup() argument
6032 if (mas_is_active(mas)) { in mas_find_rev_setup()
6033 if (mas->index > min) in mas_find_rev_setup()
6039 if (mas_is_paused(mas)) { in mas_find_rev_setup()
6040 if (unlikely(mas->index <= min)) { in mas_find_rev_setup()
6041 mas->node = MAS_NONE; in mas_find_rev_setup()
6044 mas->node = MAS_START; in mas_find_rev_setup()
6045 mas->last = --mas->index; in mas_find_rev_setup()
6046 } else if (mas_is_none(mas)) { in mas_find_rev_setup()
6047 if (mas->index <= min) in mas_find_rev_setup()
6050 mas->last = mas->index; in mas_find_rev_setup()
6051 mas->node = MAS_START; in mas_find_rev_setup()
6052 } else if (mas_is_underflow(mas) || mas_is_overflow(mas)) { in mas_find_rev_setup()
6053 if (mas->last <= min) { in mas_find_rev_setup()
6054 mas->node = MAS_UNDERFLOW; in mas_find_rev_setup()
6058 mas->node = MAS_START; in mas_find_rev_setup()
6061 if (mas_is_start(mas)) { in mas_find_rev_setup()
6063 if (mas->index < min) in mas_find_rev_setup()
6066 *entry = mas_walk(mas); in mas_find_rev_setup()
6071 if (unlikely(!mas_searchable(mas))) { in mas_find_rev_setup()
6072 if (mas_is_ptr(mas)) in mas_find_rev_setup()
6075 if (mas_is_none(mas)) { in mas_find_rev_setup()
6080 mas->last = mas->index = 0; in mas_find_rev_setup()
6081 mas->node = MAS_ROOT; in mas_find_rev_setup()
6082 *entry = mas_root(mas); in mas_find_rev_setup()
6087 if (mas->index < min) in mas_find_rev_setup()
6093 mas->node = MAS_NONE; in mas_find_rev_setup()
6110 void *mas_find_rev(struct ma_state *mas, unsigned long min) in mas_find_rev() argument
6114 if (mas_find_rev_setup(mas, min, &entry)) in mas_find_rev()
6118 return mas_prev_slot(mas, min, false, false); in mas_find_rev()
6136 void *mas_find_range_rev(struct ma_state *mas, unsigned long min) in mas_find_range_rev() argument
6140 if (mas_find_rev_setup(mas, min, &entry)) in mas_find_range_rev()
6144 return mas_prev_slot(mas, min, true, false); in mas_find_range_rev()
6159 void *mas_erase(struct ma_state *mas) in mas_erase() argument
6162 MA_WR_STATE(wr_mas, mas, NULL); in mas_erase()
6164 if (mas_is_none(mas) || mas_is_paused(mas)) in mas_erase()
6165 mas->node = MAS_START; in mas_erase()
6168 entry = mas_state_walk(mas); in mas_erase()
6174 mas_reset(mas); in mas_erase()
6177 if (mas_nomem(mas, GFP_KERNEL)) in mas_erase()
6191 bool mas_nomem(struct ma_state *mas, gfp_t gfp) in mas_nomem() argument
6192 __must_hold(mas->tree->ma_lock) in mas_nomem()
6194 if (likely(mas->node != MA_ERROR(-ENOMEM))) { in mas_nomem()
6195 mas_destroy(mas); in mas_nomem()
6199 if (gfpflags_allow_blocking(gfp) && !mt_external_lock(mas->tree)) { in mas_nomem()
6200 mtree_unlock(mas->tree); in mas_nomem()
6201 mas_alloc_nodes(mas, gfp); in mas_nomem()
6202 mtree_lock(mas->tree); in mas_nomem()
6204 mas_alloc_nodes(mas, gfp); in mas_nomem()
6207 if (!mas_allocated(mas)) in mas_nomem()
6210 mas->node = MAS_START; in mas_nomem()
6230 MA_STATE(mas, mt, index, index); in mtree_load()
6233 trace_ma_read(__func__, &mas); in mtree_load()
6236 entry = mas_start(&mas); in mtree_load()
6237 if (unlikely(mas_is_none(&mas))) in mtree_load()
6240 if (unlikely(mas_is_ptr(&mas))) { in mtree_load()
6247 entry = mtree_lookup_walk(&mas); in mtree_load()
6248 if (!entry && unlikely(mas_is_start(&mas))) in mtree_load()
6273 MA_STATE(mas, mt, index, last); in mtree_store_range()
6274 MA_WR_STATE(wr_mas, &mas, entry); in mtree_store_range()
6276 trace_ma_write(__func__, &mas, 0, entry); in mtree_store_range()
6286 if (mas_nomem(&mas, gfp)) in mtree_store_range()
6290 if (mas_is_err(&mas)) in mtree_store_range()
6291 return xa_err(mas.node); in mtree_store_range()
6373 MA_STATE(mas, mt, 0, 0); in mtree_alloc_range()
6382 ret = mas_empty_area(&mas, min, max, size); in mtree_alloc_range()
6386 mas_insert(&mas, entry); in mtree_alloc_range()
6391 if (mas_nomem(&mas, gfp)) in mtree_alloc_range()
6394 if (mas_is_err(&mas)) in mtree_alloc_range()
6395 ret = xa_err(mas.node); in mtree_alloc_range()
6397 *startp = mas.index; in mtree_alloc_range()
6411 MA_STATE(mas, mt, 0, 0); in mtree_alloc_rrange()
6420 ret = mas_empty_area_rev(&mas, min, max, size); in mtree_alloc_rrange()
6424 mas_insert(&mas, entry); in mtree_alloc_rrange()
6429 if (mas_nomem(&mas, gfp)) in mtree_alloc_rrange()
6432 if (mas_is_err(&mas)) in mtree_alloc_rrange()
6433 ret = xa_err(mas.node); in mtree_alloc_rrange()
6435 *startp = mas.index; in mtree_alloc_rrange()
6457 MA_STATE(mas, mt, index, index); in mtree_erase()
6458 trace_ma_op(__func__, &mas); in mtree_erase()
6461 entry = mas_erase(&mas); in mtree_erase()
6518 MA_STATE(mas, mt, *index, *index); in mt_find()
6524 trace_ma_read(__func__, &mas); in mt_find()
6531 entry = mas_state_walk(&mas); in mt_find()
6532 if (mas_is_start(&mas)) in mt_find()
6541 while (mas_searchable(&mas) && (mas.last < max)) { in mt_find()
6542 entry = mas_next_entry(&mas, max); in mt_find()
6552 *index = mas.last + 1; in mt_find()
6631 static inline int mas_dead_node(struct ma_state *mas, unsigned long index) in mas_dead_node() argument
6633 if (unlikely(!mas_searchable(mas) || mas_is_start(mas))) in mas_dead_node()
6636 if (likely(!mte_dead_node(mas->node))) in mas_dead_node()
6639 mas_rewalk(mas, index); in mas_dead_node()
6670 static inline struct maple_enode *mas_get_slot(struct ma_state *mas, in mas_get_slot() argument
6673 return mas_slot(mas, ma_slots(mas_mn(mas), mte_node_type(mas->node)), in mas_get_slot()
6678 static void mas_dfs_postorder(struct ma_state *mas, unsigned long max) in mas_dfs_postorder() argument
6681 struct maple_enode *p = MAS_NONE, *mn = mas->node; in mas_dfs_postorder()
6684 mas_next_node(mas, mas_mn(mas), max); in mas_dfs_postorder()
6685 if (!mas_is_none(mas)) in mas_dfs_postorder()
6691 mas->node = mn; in mas_dfs_postorder()
6692 mas_ascend(mas); in mas_dfs_postorder()
6694 p = mas->node; in mas_dfs_postorder()
6695 p_min = mas->min; in mas_dfs_postorder()
6696 p_max = mas->max; in mas_dfs_postorder()
6697 mas_prev_node(mas, 0); in mas_dfs_postorder()
6698 } while (!mas_is_none(mas)); in mas_dfs_postorder()
6700 mas->node = p; in mas_dfs_postorder()
6701 mas->max = p_max; in mas_dfs_postorder()
6702 mas->min = p_min; in mas_dfs_postorder()
6912 static void mas_validate_gaps(struct ma_state *mas) in mas_validate_gaps() argument
6914 struct maple_enode *mte = mas->node; in mas_validate_gaps()
6916 enum maple_type mt = mte_node_type(mas->node); in mas_validate_gaps()
6918 unsigned long p_end, p_start = mas->min; in mas_validate_gaps()
6926 if (mas_get_slot(mas, i)) { in mas_validate_gaps()
6939 p_end = mas_safe_pivot(mas, pivots, i, mt); in mas_validate_gaps()
6942 if (!mas_get_slot(mas, i)) in mas_validate_gaps()
6945 void *entry = mas_get_slot(mas, i); in mas_validate_gaps()
6948 MT_BUG_ON(mas->tree, !entry); in mas_validate_gaps()
6952 mas_mn(mas), i, gap, p_end, p_start, in mas_validate_gaps()
6954 MT_BUG_ON(mas->tree, gap > p_end - p_start + 1); in mas_validate_gaps()
6962 if (p_end >= mas->max) in mas_validate_gaps()
6971 MT_BUG_ON(mas->tree, 1); in mas_validate_gaps()
6977 MT_BUG_ON(mas->tree, 1); in mas_validate_gaps()
6980 MT_BUG_ON(mas->tree, !gaps); in mas_validate_gaps()
6985 MT_BUG_ON(mas->tree, 1); in mas_validate_gaps()
6993 p_slot = mte_parent_slot(mas->node); in mas_validate_gaps()
6995 MT_BUG_ON(mas->tree, max_gap > mas->max); in mas_validate_gaps()
6996 if (ma_gaps(p_mn, mas_parent_type(mas, mte))[p_slot] != max_gap) { in mas_validate_gaps()
6998 mt_dump(mas->tree, mt_dump_hex); in mas_validate_gaps()
6999 MT_BUG_ON(mas->tree, 1); in mas_validate_gaps()
7003 static void mas_validate_parent_slot(struct ma_state *mas) in mas_validate_parent_slot() argument
7012 if (mte_is_root(mas->node)) in mas_validate_parent_slot()
7015 p_slot = mte_parent_slot(mas->node); in mas_validate_parent_slot()
7016 p_type = mas_parent_type(mas, mas->node); in mas_validate_parent_slot()
7017 parent = mte_parent(mas->node); in mas_validate_parent_slot()
7019 MT_BUG_ON(mas->tree, mas_mn(mas) == parent); in mas_validate_parent_slot()
7024 node = mas_slot(mas, slots, i); in mas_validate_parent_slot()
7026 if (node != mas->node) in mas_validate_parent_slot()
7028 parent, i, mas_mn(mas)); in mas_validate_parent_slot()
7029 MT_BUG_ON(mas->tree, node != mas->node); in mas_validate_parent_slot()
7030 } else if (node == mas->node) { in mas_validate_parent_slot()
7032 mas_mn(mas), parent, i, p_slot); in mas_validate_parent_slot()
7033 MT_BUG_ON(mas->tree, node == mas->node); in mas_validate_parent_slot()
7038 static void mas_validate_child_slot(struct ma_state *mas) in mas_validate_child_slot() argument
7040 enum maple_type type = mte_node_type(mas->node); in mas_validate_child_slot()
7041 void __rcu **slots = ma_slots(mte_to_node(mas->node), type); in mas_validate_child_slot()
7042 unsigned long *pivots = ma_pivots(mte_to_node(mas->node), type); in mas_validate_child_slot()
7046 if (mte_is_leaf(mas->node)) in mas_validate_child_slot()
7050 child = mas_slot(mas, slots, i); in mas_validate_child_slot()
7054 mas_mn(mas), i); in mas_validate_child_slot()
7055 MT_BUG_ON(mas->tree, 1); in mas_validate_child_slot()
7060 mas_mn(mas), i, mte_to_node(child), in mas_validate_child_slot()
7062 MT_BUG_ON(mas->tree, 1); in mas_validate_child_slot()
7065 if (mte_parent(child) != mte_to_node(mas->node)) { in mas_validate_child_slot()
7068 mte_to_node(mas->node)); in mas_validate_child_slot()
7069 MT_BUG_ON(mas->tree, 1); in mas_validate_child_slot()
7072 if (i < mt_pivots[type] && pivots[i] == mas->max) in mas_validate_child_slot()
7082 static void mas_validate_limits(struct ma_state *mas) in mas_validate_limits() argument
7086 enum maple_type type = mte_node_type(mas->node); in mas_validate_limits()
7087 void __rcu **slots = ma_slots(mte_to_node(mas->node), type); in mas_validate_limits()
7088 unsigned long *pivots = ma_pivots(mas_mn(mas), type); in mas_validate_limits()
7093 piv = mas_safe_pivot(mas, pivots, i, type); in mas_validate_limits()
7097 mas_mn(mas), i); in mas_validate_limits()
7098 MAS_WARN_ON(mas, 1); in mas_validate_limits()
7103 mas_mn(mas), i, piv, prev_piv); in mas_validate_limits()
7104 MAS_WARN_ON(mas, piv < prev_piv); in mas_validate_limits()
7107 if (piv < mas->min) { in mas_validate_limits()
7108 pr_err("%p[%u] %lu < %lu\n", mas_mn(mas), i, in mas_validate_limits()
7109 piv, mas->min); in mas_validate_limits()
7110 MAS_WARN_ON(mas, piv < mas->min); in mas_validate_limits()
7112 if (piv > mas->max) { in mas_validate_limits()
7113 pr_err("%p[%u] %lu > %lu\n", mas_mn(mas), i, in mas_validate_limits()
7114 piv, mas->max); in mas_validate_limits()
7115 MAS_WARN_ON(mas, piv > mas->max); in mas_validate_limits()
7118 if (piv == mas->max) in mas_validate_limits()
7122 if (mas_data_end(mas) != i) { in mas_validate_limits()
7124 mas_mn(mas), mas_data_end(mas), i); in mas_validate_limits()
7125 MT_BUG_ON(mas->tree, 1); in mas_validate_limits()
7129 void *entry = mas_slot(mas, slots, i); in mas_validate_limits()
7132 pr_err("%p[%u] should not have entry %p\n", mas_mn(mas), in mas_validate_limits()
7134 MT_BUG_ON(mas->tree, entry != NULL); in mas_validate_limits()
7144 mas_mn(mas), i, piv); in mas_validate_limits()
7145 MAS_WARN_ON(mas, i < mt_pivots[type] - 1); in mas_validate_limits()
7155 MA_STATE(mas, mt, 0, 0); in mt_validate_nulls()
7157 mas_start(&mas); in mt_validate_nulls()
7158 if (mas_is_none(&mas) || (mas.node == MAS_ROOT)) in mt_validate_nulls()
7161 while (!mte_is_leaf(mas.node)) in mt_validate_nulls()
7162 mas_descend(&mas); in mt_validate_nulls()
7164 slots = ma_slots(mte_to_node(mas.node), mte_node_type(mas.node)); in mt_validate_nulls()
7166 entry = mas_slot(&mas, slots, offset); in mt_validate_nulls()
7169 mas_mn(&mas), offset); in mt_validate_nulls()
7173 if (offset == mas_data_end(&mas)) { in mt_validate_nulls()
7174 mas_next_node(&mas, mas_mn(&mas), ULONG_MAX); in mt_validate_nulls()
7175 if (mas_is_none(&mas)) in mt_validate_nulls()
7178 slots = ma_slots(mte_to_node(mas.node), in mt_validate_nulls()
7179 mte_node_type(mas.node)); in mt_validate_nulls()
7184 } while (!mas_is_none(&mas)); in mt_validate_nulls()
7196 MA_STATE(mas, mt, 0, 0); in mt_validate()
7198 mas_start(&mas); in mt_validate()
7199 if (!mas_searchable(&mas)) in mt_validate()
7202 while (!mte_is_leaf(mas.node)) in mt_validate()
7203 mas_descend(&mas); in mt_validate()
7205 while (!mas_is_none(&mas)) { in mt_validate()
7206 MAS_WARN_ON(&mas, mte_dead_node(mas.node)); in mt_validate()
7207 end = mas_data_end(&mas); in mt_validate()
7208 if (MAS_WARN_ON(&mas, (end < mt_min_slot_count(mas.node)) && in mt_validate()
7209 (mas.max != ULONG_MAX))) { in mt_validate()
7210 pr_err("Invalid size %u of %p\n", end, mas_mn(&mas)); in mt_validate()
7213 mas_validate_parent_slot(&mas); in mt_validate()
7214 mas_validate_limits(&mas); in mt_validate()
7215 mas_validate_child_slot(&mas); in mt_validate()
7217 mas_validate_gaps(&mas); in mt_validate()
7218 mas_dfs_postorder(&mas, ULONG_MAX); in mt_validate()
7227 void mas_dump(const struct ma_state *mas) in mas_dump() argument
7229 pr_err("MAS: tree=%p enode=%p ", mas->tree, mas->node); in mas_dump()
7230 if (mas_is_none(mas)) in mas_dump()
7232 else if (mas_is_ptr(mas)) in mas_dump()
7234 else if (mas_is_start(mas)) in mas_dump()
7236 else if (mas_is_paused(mas)) in mas_dump()
7239 pr_err("[%u] index=%lx last=%lx\n", mas->offset, mas->index, mas->last); in mas_dump()
7241 mas->min, mas->max, mas->alloc, mas->depth, mas->mas_flags); in mas_dump()
7242 if (mas->index > mas->last) in mas_dump()