Lines Matching refs:mas
214 static void mas_set_height(struct ma_state *mas) in mas_set_height() argument
216 unsigned int new_flags = mas->tree->ma_flags; in mas_set_height()
219 MAS_BUG_ON(mas, mas->depth > MAPLE_HEIGHT_MAX); in mas_set_height()
220 new_flags |= mas->depth << MT_FLAGS_HEIGHT_OFFSET; in mas_set_height()
221 mas->tree->ma_flags = new_flags; in mas_set_height()
224 static unsigned int mas_mt_height(struct ma_state *mas) in mas_mt_height() argument
226 return mt_height(mas->tree); in mas_mt_height()
266 static __always_inline void mas_set_err(struct ma_state *mas, long err) in mas_set_err() argument
268 mas->node = MA_ERROR(err); in mas_set_err()
269 mas->status = ma_error; in mas_set_err()
272 static __always_inline bool mas_is_ptr(const struct ma_state *mas) in mas_is_ptr() argument
274 return mas->status == ma_root; in mas_is_ptr()
277 static __always_inline bool mas_is_start(const struct ma_state *mas) in mas_is_start() argument
279 return mas->status == ma_start; in mas_is_start()
282 static __always_inline bool mas_is_none(const struct ma_state *mas) in mas_is_none() argument
284 return mas->status == ma_none; in mas_is_none()
287 static __always_inline bool mas_is_paused(const struct ma_state *mas) in mas_is_paused() argument
289 return mas->status == ma_pause; in mas_is_paused()
292 static __always_inline bool mas_is_overflow(struct ma_state *mas) in mas_is_overflow() argument
294 return mas->status == ma_overflow; in mas_is_overflow()
297 static inline bool mas_is_underflow(struct ma_state *mas) in mas_is_underflow() argument
299 return mas->status == ma_underflow; in mas_is_underflow()
326 static inline struct maple_node *mas_mn(const struct ma_state *mas) in mas_mn() argument
328 return mte_to_node(mas->node); in mas_mn()
390 static inline bool mas_is_root_limits(const struct ma_state *mas) in mas_is_root_limits() argument
392 return !mas->min && mas->max == ULONG_MAX; in mas_is_root_limits()
469 enum maple_type mas_parent_type(struct ma_state *mas, struct maple_enode *enode) in mas_parent_type() argument
481 if (mt_is_alloc(mas->tree)) in mas_parent_type()
500 void mas_set_parent(struct ma_state *mas, struct maple_enode *enode, in mas_set_parent() argument
508 MAS_BUG_ON(mas, p_type == maple_dense); in mas_set_parent()
509 MAS_BUG_ON(mas, p_type == maple_leaf_64); in mas_set_parent()
604 static inline unsigned long mas_allocated(const struct ma_state *mas) in mas_allocated() argument
606 if (!mas->alloc || ((unsigned long)mas->alloc & 0x1)) in mas_allocated()
609 return mas->alloc->total; in mas_allocated()
622 static inline void mas_set_alloc_req(struct ma_state *mas, unsigned long count) in mas_set_alloc_req() argument
624 if (!mas->alloc || ((unsigned long)mas->alloc & 0x1)) { in mas_set_alloc_req()
626 mas->alloc = NULL; in mas_set_alloc_req()
628 mas->alloc = (struct maple_alloc *)(((count) << 1U) | 1U); in mas_set_alloc_req()
632 mas->alloc->request_count = count; in mas_set_alloc_req()
645 static inline unsigned int mas_alloc_req(const struct ma_state *mas) in mas_alloc_req() argument
647 if ((unsigned long)mas->alloc & 0x1) in mas_alloc_req()
648 return (unsigned long)(mas->alloc) >> 1; in mas_alloc_req()
649 else if (mas->alloc) in mas_alloc_req()
650 return mas->alloc->request_count; in mas_alloc_req()
710 mas_safe_pivot(const struct ma_state *mas, unsigned long *pivots, in mas_safe_pivot() argument
714 return mas->max; in mas_safe_pivot()
728 mas_safe_min(struct ma_state *mas, unsigned long *pivots, unsigned char offset) in mas_safe_min() argument
733 return mas->min; in mas_safe_min()
816 static __always_inline void *mas_slot_locked(struct ma_state *mas, in mas_slot_locked() argument
819 return mt_slot_locked(mas->tree, slots, offset); in mas_slot_locked()
830 static __always_inline void *mas_slot(struct ma_state *mas, void __rcu **slots, in mas_slot() argument
833 return mt_slot(mas->tree, slots, offset); in mas_slot()
842 static __always_inline void *mas_root(struct ma_state *mas) in mas_root() argument
844 return rcu_dereference_check(mas->tree->ma_root, mt_locked(mas->tree)); in mas_root()
858 static inline void *mas_root_locked(struct ma_state *mas) in mas_root_locked() argument
860 return mt_root_locked(mas->tree); in mas_root_locked()
995 static void mas_mat_destroy(struct ma_state *mas, struct ma_topiary *mat) in mas_mat_destroy() argument
999 bool in_rcu = mt_in_rcu(mas->tree); in mas_mat_destroy()
1004 mt_destroy_walk(mat->head, mas->tree, !in_rcu); in mas_mat_destroy()
1016 static inline void mas_descend(struct ma_state *mas) in mas_descend() argument
1023 node = mas_mn(mas); in mas_descend()
1024 type = mte_node_type(mas->node); in mas_descend()
1028 if (mas->offset) in mas_descend()
1029 mas->min = pivots[mas->offset - 1] + 1; in mas_descend()
1030 mas->max = mas_safe_pivot(mas, pivots, mas->offset, type); in mas_descend()
1031 mas->node = mas_slot(mas, slots, mas->offset); in mas_descend()
1061 static int mas_ascend(struct ma_state *mas) in mas_ascend() argument
1073 a_node = mas_mn(mas); in mas_ascend()
1075 mas->offset = 0; in mas_ascend()
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()
1094 mas->max = ULONG_MAX; in mas_ascend()
1095 mas->min = 0; in mas_ascend()
1101 if (!mas->offset) { in mas_ascend()
1102 min = mas->min; in mas_ascend()
1106 if (mas->max == ULONG_MAX) in mas_ascend()
1111 a_type = mas_parent_type(mas, p_enode); in mas_ascend()
1138 mas->max = max; in mas_ascend()
1139 mas->min = min; in mas_ascend()
1149 static inline struct maple_node *mas_pop_node(struct ma_state *mas) in mas_pop_node() argument
1151 struct maple_alloc *ret, *node = mas->alloc; in mas_pop_node()
1152 unsigned long total = mas_allocated(mas); in mas_pop_node()
1153 unsigned int req = mas_alloc_req(mas); in mas_pop_node()
1161 mas->alloc = NULL; in mas_pop_node()
1168 mas->alloc = node->slot[0]; in mas_pop_node()
1169 mas->alloc->total = node->total - 1; in mas_pop_node()
1181 mas_set_alloc_req(mas, req); in mas_pop_node()
1196 static inline void mas_push_node(struct ma_state *mas, struct maple_node *used) in mas_push_node() argument
1199 struct maple_alloc *head = mas->alloc; in mas_push_node()
1201 unsigned int requested = mas_alloc_req(mas); in mas_push_node()
1203 count = mas_allocated(mas); in mas_push_node()
1218 mas->alloc = reuse; in mas_push_node()
1221 mas_set_alloc_req(mas, requested - 1); in mas_push_node()
1229 static inline void mas_alloc_nodes(struct ma_state *mas, gfp_t gfp) in mas_alloc_nodes() argument
1232 unsigned long allocated = mas_allocated(mas); in mas_alloc_nodes()
1233 unsigned int requested = mas_alloc_req(mas); in mas_alloc_nodes()
1241 mas_set_alloc_req(mas, 0); in mas_alloc_nodes()
1242 if (mas->mas_flags & MA_STATE_PREALLOC) { in mas_alloc_nodes()
1248 if (!allocated || mas->alloc->node_count == MAPLE_ALLOC_SLOTS) { in mas_alloc_nodes()
1254 node->slot[0] = mas->alloc; in mas_alloc_nodes()
1260 mas->alloc = node; in mas_alloc_nodes()
1266 node = mas->alloc; in mas_alloc_nodes()
1288 mas->alloc->total = allocated; in mas_alloc_nodes()
1294 mas->alloc->total = allocated; in mas_alloc_nodes()
1296 mas_set_alloc_req(mas, requested); in mas_alloc_nodes()
1297 mas_set_err(mas, -ENOMEM); in mas_alloc_nodes()
1308 static inline void mas_free(struct ma_state *mas, struct maple_enode *used) in mas_free() argument
1312 if (mt_in_rcu(mas->tree)) in mas_free()
1315 mas_push_node(mas, tmp); in mas_free()
1325 static void mas_node_count_gfp(struct ma_state *mas, int count, gfp_t gfp) in mas_node_count_gfp() argument
1327 unsigned long allocated = mas_allocated(mas); in mas_node_count_gfp()
1330 mas_set_alloc_req(mas, count - allocated); in mas_node_count_gfp()
1331 mas_alloc_nodes(mas, gfp); in mas_node_count_gfp()
1343 static void mas_node_count(struct ma_state *mas, int count) in mas_node_count() argument
1345 return mas_node_count_gfp(mas, count, GFP_NOWAIT | __GFP_NOWARN); in mas_node_count()
1361 static inline struct maple_enode *mas_start(struct ma_state *mas) in mas_start() argument
1363 if (likely(mas_is_start(mas))) { in mas_start()
1366 mas->min = 0; in mas_start()
1367 mas->max = ULONG_MAX; in mas_start()
1370 mas->depth = 0; in mas_start()
1371 root = mas_root(mas); in mas_start()
1374 mas->depth = 1; in mas_start()
1375 mas->status = ma_active; in mas_start()
1376 mas->node = mte_safe_root(root); in mas_start()
1377 mas->offset = 0; in mas_start()
1378 if (mte_dead_node(mas->node)) in mas_start()
1384 mas->node = NULL; in mas_start()
1387 mas->status = ma_none; in mas_start()
1388 mas->offset = MAPLE_NODE_SLOTS; in mas_start()
1393 mas->status = ma_root; in mas_start()
1394 mas->offset = MAPLE_NODE_SLOTS; in mas_start()
1397 if (mas->index > 0) in mas_start()
1446 static inline unsigned char mas_data_end(struct ma_state *mas) in mas_data_end() argument
1453 type = mte_node_type(mas->node); in mas_data_end()
1454 node = mas_mn(mas); in mas_data_end()
1466 if (likely(pivots[offset] == mas->max)) in mas_data_end()
1478 static unsigned long mas_leaf_max_gap(struct ma_state *mas) in mas_leaf_max_gap() argument
1488 mt = mte_node_type(mas->node); in mas_leaf_max_gap()
1489 mn = mas_mn(mas); in mas_leaf_max_gap()
1514 max_gap = pivots[0] - mas->min + 1; in mas_leaf_max_gap()
1521 max_piv = ma_data_end(mn, mt, pivots, mas->max) - 1; in mas_leaf_max_gap()
1526 if (unlikely(mas->max == ULONG_MAX) && !slots[max_piv + 1]) { in mas_leaf_max_gap()
1531 if (max_gap > pivots[max_piv] - mas->min) in mas_leaf_max_gap()
1587 static inline unsigned long mas_max_gap(struct ma_state *mas) in mas_max_gap() argument
1594 mt = mte_node_type(mas->node); in mas_max_gap()
1596 return mas_leaf_max_gap(mas); in mas_max_gap()
1598 node = mas_mn(mas); in mas_max_gap()
1599 MAS_BUG_ON(mas, mt != maple_arange_64); in mas_max_gap()
1614 static inline void mas_parent_gap(struct ma_state *mas, unsigned char offset, in mas_parent_gap() argument
1624 pnode = mte_parent(mas->node); in mas_parent_gap()
1625 pmt = mas_parent_type(mas, mas->node); in mas_parent_gap()
1630 MAS_BUG_ON(mas, pmt != maple_arange_64); in mas_parent_gap()
1654 pmt = mas_parent_type(mas, penode); in mas_parent_gap()
1665 static inline void mas_update_gap(struct ma_state *mas) in mas_update_gap() argument
1671 if (!mt_is_alloc(mas->tree)) in mas_update_gap()
1674 if (mte_is_root(mas->node)) in mas_update_gap()
1677 max_gap = mas_max_gap(mas); in mas_update_gap()
1679 pslot = mte_parent_slot(mas->node); in mas_update_gap()
1680 p_gap = ma_gaps(mte_parent(mas->node), in mas_update_gap()
1681 mas_parent_type(mas, mas->node))[pslot]; in mas_update_gap()
1684 mas_parent_gap(mas, pslot, max_gap); in mas_update_gap()
1693 static inline void mas_adopt_children(struct ma_state *mas, in mas_adopt_children() argument
1703 offset = ma_data_end(node, type, pivots, mas->max); in mas_adopt_children()
1705 child = mas_slot_locked(mas, slots, offset); in mas_adopt_children()
1706 mas_set_parent(mas, child, parent, offset); in mas_adopt_children()
1716 static inline void mas_put_in_tree(struct ma_state *mas, in mas_put_in_tree() argument
1718 __must_hold(mas->tree->ma_lock) in mas_put_in_tree()
1723 if (mte_is_root(mas->node)) { in mas_put_in_tree()
1724 mas_mn(mas)->parent = ma_parent_ptr(mas_tree_parent(mas)); in mas_put_in_tree()
1725 rcu_assign_pointer(mas->tree->ma_root, mte_mk_root(mas->node)); in mas_put_in_tree()
1726 mas_set_height(mas); in mas_put_in_tree()
1729 offset = mte_parent_slot(mas->node); in mas_put_in_tree()
1730 slots = ma_slots(mte_parent(mas->node), in mas_put_in_tree()
1731 mas_parent_type(mas, mas->node)); in mas_put_in_tree()
1732 rcu_assign_pointer(slots[offset], mas->node); in mas_put_in_tree()
1745 static inline void mas_replace_node(struct ma_state *mas, in mas_replace_node() argument
1747 __must_hold(mas->tree->ma_lock) in mas_replace_node()
1749 mas_put_in_tree(mas, old_enode); in mas_replace_node()
1750 mas_free(mas, old_enode); in mas_replace_node()
1758 static inline bool mas_find_child(struct ma_state *mas, struct ma_state *child) in mas_find_child() argument
1759 __must_hold(mas->tree->ma_lock) in mas_find_child()
1769 mt = mte_node_type(mas->node); in mas_find_child()
1770 node = mas_mn(mas); in mas_find_child()
1773 end = ma_data_end(node, mt, pivots, mas->max); in mas_find_child()
1774 for (offset = mas->offset; offset <= end; offset++) { in mas_find_child()
1775 entry = mas_slot_locked(mas, slots, offset); in mas_find_child()
1777 *child = *mas; in mas_find_child()
1778 mas->offset = offset + 1; in mas_find_child()
1861 static inline int mab_calc_split(struct ma_state *mas, in mab_calc_split() argument
1874 if (unlikely((mas->mas_flags & MA_STATE_BULK))) { in mab_calc_split()
1881 mas->mas_flags |= MA_STATE_REBALANCE; in mab_calc_split()
1920 static inline void mas_mab_cp(struct ma_state *mas, unsigned char mas_start, in mas_mab_cp() argument
1931 node = mas_mn(mas); in mas_mab_cp()
1932 mt = mte_node_type(mas->node); in mas_mab_cp()
1947 if (unlikely(mas->max == b_node->pivot[j])) in mas_mab_cp()
1951 b_node->pivot[j] = mas_safe_pivot(mas, pivots, i, mt); in mas_mab_cp()
1958 if (!ma_is_leaf(mt) && mt_is_alloc(mas->tree)) { in mas_mab_cp()
1987 struct ma_state *mas, bool new_max) in mab_mas_cp() argument
1990 enum maple_type mt = mte_node_type(mas->node); in mab_mas_cp()
1991 struct maple_node *node = mte_to_node(mas->node); in mab_mas_cp()
2012 mas->max = b_node->pivot[i - 1]; in mab_mas_cp()
2015 if (likely(!ma_is_leaf(mt) && mt_is_alloc(mas->tree))) { in mab_mas_cp()
2040 static inline void mas_bulk_rebalance(struct ma_state *mas, unsigned char end, in mas_bulk_rebalance() argument
2043 if (!(mas->mas_flags & MA_STATE_BULK)) in mas_bulk_rebalance()
2046 if (mte_is_root(mas->node)) in mas_bulk_rebalance()
2050 mas->mas_flags &= ~MA_STATE_REBALANCE; in mas_bulk_rebalance()
2071 struct ma_state *mas = wr_mas->mas; in mas_store_b_node() local
2075 slot = mas->offset; in mas_store_b_node()
2078 mas_mab_cp(mas, 0, slot - 1, b_node, 0); in mas_store_b_node()
2082 piv = mas->min - 1; in mas_store_b_node()
2084 if (piv + 1 < mas->index) { in mas_store_b_node()
2088 b_node->gap[b_end] = mas->index - 1 - piv; in mas_store_b_node()
2089 b_node->pivot[b_end++] = mas->index - 1; in mas_store_b_node()
2093 mas->offset = b_end; in mas_store_b_node()
2095 b_node->pivot[b_end] = mas->last; in mas_store_b_node()
2098 if (mas->last >= mas->max) in mas_store_b_node()
2102 piv = mas_safe_pivot(mas, wr_mas->pivots, offset_end, wr_mas->type); in mas_store_b_node()
2103 if (piv > mas->last) { in mas_store_b_node()
2105 mas_bulk_rebalance(mas, b_node->b_end, wr_mas->type); in mas_store_b_node()
2108 wr_mas->content = mas_slot_locked(mas, wr_mas->slots, in mas_store_b_node()
2113 b_node->gap[b_end] = piv - mas->last + 1; in mas_store_b_node()
2118 if (slot > mas->end) in mas_store_b_node()
2122 mas_mab_cp(mas, slot, mas->end + 1, b_node, ++b_end); in mas_store_b_node()
2136 static inline bool mas_prev_sibling(struct ma_state *mas) in mas_prev_sibling() argument
2138 unsigned int p_slot = mte_parent_slot(mas->node); in mas_prev_sibling()
2144 mas_ascend(mas); in mas_prev_sibling()
2145 mas->offset = p_slot - 1; in mas_prev_sibling()
2146 mas_descend(mas); in mas_prev_sibling()
2156 static inline bool mas_next_sibling(struct ma_state *mas) in mas_next_sibling() argument
2158 MA_STATE(parent, mas->tree, mas->index, mas->last); in mas_next_sibling()
2160 if (mte_is_root(mas->node)) in mas_next_sibling()
2163 parent = *mas; in mas_next_sibling()
2165 parent.offset = mte_parent_slot(mas->node) + 1; in mas_next_sibling()
2169 *mas = parent; in mas_next_sibling()
2170 mas_descend(mas); in mas_next_sibling()
2181 static inline void mas_node_or_none(struct ma_state *mas, in mas_node_or_none() argument
2185 mas->node = enode; in mas_node_or_none()
2186 mas->status = ma_active; in mas_node_or_none()
2188 mas->node = NULL; in mas_node_or_none()
2189 mas->status = ma_none; in mas_node_or_none()
2203 struct ma_state *mas = wr_mas->mas; in mas_wr_node_walk() local
2207 wr_mas->r_max = wr_mas->r_min = mas->index; in mas_wr_node_walk()
2208 mas->offset = mas->index = mas->min; in mas_wr_node_walk()
2212 wr_mas->node = mas_mn(wr_mas->mas); in mas_wr_node_walk()
2214 count = mas->end = ma_data_end(wr_mas->node, wr_mas->type, in mas_wr_node_walk()
2215 wr_mas->pivots, mas->max); in mas_wr_node_walk()
2216 offset = mas->offset; in mas_wr_node_walk()
2218 while (offset < count && mas->index > wr_mas->pivots[offset]) in mas_wr_node_walk()
2221 wr_mas->r_max = offset < count ? wr_mas->pivots[offset] : mas->max; in mas_wr_node_walk()
2222 wr_mas->r_min = mas_safe_min(mas, wr_mas->pivots, offset); in mas_wr_node_walk()
2223 wr_mas->offset_end = mas->offset = offset; in mas_wr_node_walk()
2327 wr_mas.mas = mast->orig_l; in mast_ascend()
2345 *mas_new_ma_node(struct ma_state *mas, struct maple_big_node *b_node) in mas_new_ma_node() argument
2347 return mt_mk_node(ma_mnode_ptr(mas_pop_node(mas)), b_node->type); in mas_new_ma_node()
2362 static inline unsigned char mas_mab_to_node(struct ma_state *mas, in mas_mab_to_node() argument
2370 *left = mas_new_ma_node(mas, b_node); in mas_mab_to_node()
2378 split = mab_calc_split(mas, b_node, mid_split); in mas_mab_to_node()
2379 *right = mas_new_ma_node(mas, b_node); in mas_mab_to_node()
2383 *middle = mas_new_ma_node(mas, b_node); in mas_mab_to_node()
2397 struct ma_state *mas, in mab_set_b_end() argument
2404 if (mt_is_alloc(mas->tree)) in mab_set_b_end()
2405 b_node->gap[b_node->b_end] = mas_max_gap(mas); in mab_set_b_end()
2406 b_node->pivot[b_node->b_end++] = mas->max; in mab_set_b_end()
2419 static inline void mas_set_split_parent(struct ma_state *mas, in mas_set_split_parent() argument
2424 if (mas_is_none(mas)) in mas_set_split_parent()
2428 mas_set_parent(mas, mas->node, left, *slot); in mas_set_split_parent()
2430 mas_set_parent(mas, mas->node, right, (*slot) - split - 1); in mas_set_split_parent()
2506 static inline void mas_topiary_node(struct ma_state *mas, in mas_topiary_node() argument
2521 mas_push_node(mas, tmp); in mas_topiary_node()
2541 static inline void mas_topiary_replace(struct ma_state *mas, in mas_topiary_replace() argument
2545 MA_TOPIARY(subtrees, mas->tree); in mas_topiary_replace()
2550 mas_put_in_tree(mas, old_enode); in mas_topiary_replace()
2553 tmp[0] = *mas; in mas_topiary_replace()
2572 if (MAS_WARN_ON(mas, n == 0)) in mas_topiary_replace()
2584 return mas_free(mas, old_enode); in mas_topiary_replace()
2586 tmp[0] = *mas; in mas_topiary_replace()
2591 in_rcu = mt_in_rcu(mas->tree); in mas_topiary_replace()
2612 if (MAS_WARN_ON(mas, n == 0)) in mas_topiary_replace()
2619 mas_topiary_node(mas, &tmp[i], in_rcu); in mas_topiary_replace()
2625 mas_topiary_node(mas, &tmp[i], in_rcu); in mas_topiary_replace()
2627 mas_mat_destroy(mas, &subtrees); in mas_topiary_replace()
2637 static inline void mas_wmb_replace(struct ma_state *mas, in mas_wmb_replace() argument
2641 mas_topiary_replace(mas, old_enode); in mas_wmb_replace()
2643 if (mte_is_leaf(mas->node)) in mas_wmb_replace()
2646 mas_update_gap(mas); in mas_wmb_replace()
2746 static inline void *mtree_range_walk(struct ma_state *mas) in mtree_range_walk() argument
2758 next = mas->node; in mtree_range_walk()
2759 min = mas->min; in mtree_range_walk()
2760 max = mas->max; in mtree_range_walk()
2769 if (pivots[0] >= mas->index) { in mtree_range_walk()
2777 if (pivots[offset] >= mas->index) { in mtree_range_walk()
2787 next = mt_slot(mas->tree, slots, offset); in mtree_range_walk()
2792 mas->end = end; in mtree_range_walk()
2793 mas->offset = offset; in mtree_range_walk()
2794 mas->index = min; in mtree_range_walk()
2795 mas->last = max; in mtree_range_walk()
2796 mas->min = prev_min; in mtree_range_walk()
2797 mas->max = prev_max; in mtree_range_walk()
2798 mas->node = last; in mtree_range_walk()
2802 mas_reset(mas); in mtree_range_walk()
2822 static void mas_spanning_rebalance(struct ma_state *mas, in mas_spanning_rebalance() argument
2830 MA_STATE(l_mas, mas->tree, mas->index, mas->index); in mas_spanning_rebalance()
2831 MA_STATE(r_mas, mas->tree, mas->index, mas->last); in mas_spanning_rebalance()
2832 MA_STATE(m_mas, mas->tree, mas->index, mas->index); in mas_spanning_rebalance()
2864 split = mas_mab_to_node(mas, mast->bn, &left, &right, &middle, in mas_spanning_rebalance()
2910 l_mas.node = mt_mk_node(ma_mnode_ptr(mas_pop_node(mas)), in mas_spanning_rebalance()
2914 mas_set_parent(mas, left, l_mas.node, slot); in mas_spanning_rebalance()
2916 mas_set_parent(mas, middle, l_mas.node, ++slot); in mas_spanning_rebalance()
2919 mas_set_parent(mas, right, l_mas.node, ++slot); in mas_spanning_rebalance()
2923 mas_mn(mast->l)->parent = ma_parent_ptr(mas_tree_parent(mas)); in mas_spanning_rebalance()
2931 mas->depth = l_mas.depth; in mas_spanning_rebalance()
2932 mas->node = l_mas.node; in mas_spanning_rebalance()
2933 mas->min = l_mas.min; in mas_spanning_rebalance()
2934 mas->max = l_mas.max; in mas_spanning_rebalance()
2935 mas->offset = l_mas.offset; in mas_spanning_rebalance()
2936 mas_wmb_replace(mas, old_enode); in mas_spanning_rebalance()
2937 mtree_range_walk(mas); in mas_spanning_rebalance()
2949 static inline void mas_rebalance(struct ma_state *mas, in mas_rebalance() argument
2952 char empty_count = mas_mt_height(mas); in mas_rebalance()
2956 MA_STATE(l_mas, mas->tree, mas->index, mas->last); in mas_rebalance()
2957 MA_STATE(r_mas, mas->tree, mas->index, mas->last); in mas_rebalance()
2959 trace_ma_op(__func__, mas); in mas_rebalance()
2974 mast.bn->type = mte_node_type(mas->node); in mas_rebalance()
2976 l_mas = r_mas = *mas; in mas_rebalance()
2985 mas->offset += shift; in mas_rebalance()
2991 return mas_spanning_rebalance(mas, &mast, empty_count); in mas_rebalance()
3003 static inline void mas_destroy_rebalance(struct ma_state *mas, unsigned char end) in mas_destroy_rebalance() argument
3005 enum maple_type mt = mte_node_type(mas->node); in mas_destroy_rebalance()
3011 bool in_rcu = mt_in_rcu(mas->tree); in mas_destroy_rebalance()
3013 MA_STATE(l_mas, mas->tree, mas->index, mas->last); in mas_destroy_rebalance()
3015 l_mas = *mas; in mas_destroy_rebalance()
3020 newnode = mas_pop_node(mas); in mas_destroy_rebalance()
3025 node = mas_mn(mas); in mas_destroy_rebalance()
3043 mas->min = l_mas.max + 1; in mas_destroy_rebalance()
3074 mas->node = mt_mk_node(newnode, mt); in mas_destroy_rebalance()
3077 new_left = mas_pop_node(mas); in mas_destroy_rebalance()
3088 offset = mte_parent_slot(mas->node); in mas_destroy_rebalance()
3090 parent = mas_pop_node(mas); in mas_destroy_rebalance()
3094 rcu_assign_pointer(slots[offset], mas->node); in mas_destroy_rebalance()
3099 gap = mas_leaf_max_gap(mas); in mas_destroy_rebalance()
3100 mte_set_gap(eparent, mte_parent_slot(mas->node), gap); in mas_destroy_rebalance()
3103 mas_ascend(mas); in mas_destroy_rebalance()
3106 mas_replace_node(mas, old_eparent); in mas_destroy_rebalance()
3107 mas_adopt_children(mas, mas->node); in mas_destroy_rebalance()
3110 mas_update_gap(mas); in mas_destroy_rebalance()
3120 struct ma_state *mas, int height) in mas_split_final_node() argument
3124 if (mte_is_root(mas->node)) { in mas_split_final_node()
3125 if (mt_is_alloc(mas->tree)) in mas_split_final_node()
3129 mas->depth = height; in mas_split_final_node()
3135 ancestor = mas_new_ma_node(mas, mast->bn); in mas_split_final_node()
3136 mas_set_parent(mas, mast->l->node, ancestor, mast->l->offset); in mas_split_final_node()
3137 mas_set_parent(mas, mast->r->node, ancestor, mast->r->offset); in mas_split_final_node()
3138 mte_to_node(ancestor)->parent = mas_mn(mas)->parent; in mas_split_final_node()
3142 mas->offset = mast->bn->b_end - 1; in mas_split_final_node()
3152 struct ma_state *mas, in mast_fill_bnode() argument
3160 if (mte_is_root(mas->node)) { in mast_fill_bnode()
3163 mas_ascend(mas); in mast_fill_bnode()
3164 mas->offset = mte_parent_slot(mas->node); in mast_fill_bnode()
3168 mas_mab_cp(mas, 0, mast->l->offset - 1, mast->bn, 0); in mast_fill_bnode()
3174 if (mast->bn->pivot[mast->bn->b_end - 1] == mas->max) in mast_fill_bnode()
3178 mas_mab_cp(mas, split + skip, mt_slot_count(mas->node) - 1, in mast_fill_bnode()
3182 mast->bn->type = mte_node_type(mas->node); in mast_fill_bnode()
3193 struct ma_state *mas, unsigned char split) in mast_split_data() argument
3200 mast->l->offset = mte_parent_slot(mas->node); in mast_split_data()
3203 if (mte_is_leaf(mas->node)) in mast_split_data()
3225 static inline bool mas_push_data(struct ma_state *mas, int height, in mas_push_data() argument
3231 MA_STATE(tmp_mas, mas->tree, mas->index, mas->last); in mas_push_data()
3232 tmp_mas = *mas; in mas_push_data()
3242 space = 2 * mt_slot_count(mas->node) - 2; in mas_push_data()
3247 if (mas->max == ULONG_MAX) in mas_push_data()
3267 *mas = tmp_mas; in mas_push_data()
3281 mast_split_data(mast, mas, split); in mas_push_data()
3282 mast_fill_bnode(mast, mas, 2); in mas_push_data()
3283 mas_split_final_node(mast, mas, height + 1); in mas_push_data()
3292 static void mas_split(struct ma_state *mas, struct maple_big_node *b_node) in mas_split() argument
3316 MA_STATE(l_mas, mas->tree, mas->index, mas->last); in mas_split()
3317 MA_STATE(r_mas, mas->tree, mas->index, mas->last); in mas_split()
3318 MA_STATE(prev_l_mas, mas->tree, mas->index, mas->last); in mas_split()
3319 MA_STATE(prev_r_mas, mas->tree, mas->index, mas->last); in mas_split()
3321 trace_ma_op(__func__, mas); in mas_split()
3322 mas->depth = mas_mt_height(mas); in mas_split()
3330 while (height++ <= mas->depth) { in mas_split()
3332 mas_split_final_node(&mast, mas, height); in mas_split()
3336 l_mas = r_mas = *mas; in mas_split()
3337 l_mas.node = mas_new_ma_node(mas, b_node); in mas_split()
3338 r_mas.node = mas_new_ma_node(mas, b_node); in mas_split()
3347 if (mas_push_data(mas, height, &mast, true)) in mas_split()
3350 if (mas_push_data(mas, height, &mast, false)) in mas_split()
3353 split = mab_calc_split(mas, b_node, &mid_split); in mas_split()
3354 mast_split_data(&mast, mas, split); in mas_split()
3359 mast.r->max = mas->max; in mas_split()
3360 mast_fill_bnode(&mast, mas, 1); in mas_split()
3366 old = mas->node; in mas_split()
3367 mas->node = l_mas.node; in mas_split()
3368 mas_wmb_replace(mas, old); in mas_split()
3369 mtree_range_walk(mas); in mas_split()
3381 enum store_type type = wr_mas->mas->store_type; in mas_commit_b_node()
3386 return mas_rebalance(wr_mas->mas, b_node); in mas_commit_b_node()
3388 return mas_split(wr_mas->mas, b_node); in mas_commit_b_node()
3396 static inline void mas_root_expand(struct ma_state *mas, void *entry) in mas_root_expand() argument
3398 void *contents = mas_root_locked(mas); in mas_root_expand()
3405 node = mas_pop_node(mas); in mas_root_expand()
3408 node->parent = ma_parent_ptr(mas_tree_parent(mas)); in mas_root_expand()
3409 mas->node = mt_mk_node(node, type); in mas_root_expand()
3410 mas->status = ma_active; in mas_root_expand()
3412 if (mas->index) { in mas_root_expand()
3415 if (likely(mas->index > 1)) in mas_root_expand()
3418 pivots[slot++] = mas->index - 1; in mas_root_expand()
3422 mas->offset = slot; in mas_root_expand()
3423 pivots[slot] = mas->last; in mas_root_expand()
3424 if (mas->last != ULONG_MAX) in mas_root_expand()
3427 mas->depth = 1; in mas_root_expand()
3428 mas_set_height(mas); in mas_root_expand()
3431 rcu_assign_pointer(mas->tree->ma_root, mte_mk_root(mas->node)); in mas_root_expand()
3443 static inline void mas_store_root(struct ma_state *mas, void *entry) in mas_store_root() argument
3446 if (!mas->index) in mas_store_root()
3447 rcu_assign_pointer(mas->tree->ma_root, NULL); in mas_store_root()
3448 } else if (likely((mas->last != 0) || (mas->index != 0))) in mas_store_root()
3449 mas_root_expand(mas, entry); in mas_store_root()
3451 mas_root_expand(mas, entry); in mas_store_root()
3453 rcu_assign_pointer(mas->tree->ma_root, entry); in mas_store_root()
3454 mas->status = ma_start; in mas_store_root()
3471 unsigned long last = wr_mas->mas->last; in mas_is_span_wr()
3480 max = wr_mas->mas->max; in mas_is_span_wr()
3494 trace_ma_write(__func__, wr_mas->mas, wr_mas->r_max, entry); in mas_is_span_wr()
3500 wr_mas->type = mte_node_type(wr_mas->mas->node); in mas_wr_walk_descend()
3507 wr_mas->mas->max = wr_mas->r_max; in mas_wr_walk_traverse()
3508 wr_mas->mas->min = wr_mas->r_min; in mas_wr_walk_traverse()
3509 wr_mas->mas->node = wr_mas->content; in mas_wr_walk_traverse()
3510 wr_mas->mas->offset = 0; in mas_wr_walk_traverse()
3511 wr_mas->mas->depth++; in mas_wr_walk_traverse()
3523 struct ma_state *mas = wr_mas->mas; in mas_wr_walk() local
3530 wr_mas->content = mas_slot_locked(mas, wr_mas->slots, in mas_wr_walk()
3531 mas->offset); in mas_wr_walk()
3543 struct ma_state *mas = wr_mas->mas; in mas_wr_walk_index() local
3547 wr_mas->content = mas_slot_locked(mas, wr_mas->slots, in mas_wr_walk_index()
3548 mas->offset); in mas_wr_walk_index()
3562 struct ma_state *r_mas = r_wr_mas->mas; in mas_extend_spanning_null()
3563 struct ma_state *l_mas = l_wr_mas->mas; in mas_extend_spanning_null()
3594 static inline void *mas_state_walk(struct ma_state *mas) in mas_state_walk() argument
3598 entry = mas_start(mas); in mas_state_walk()
3599 if (mas_is_none(mas)) in mas_state_walk()
3602 if (mas_is_ptr(mas)) in mas_state_walk()
3605 return mtree_range_walk(mas); in mas_state_walk()
3617 static inline void *mtree_lookup_walk(struct ma_state *mas) in mtree_lookup_walk() argument
3627 next = mas->node; in mtree_lookup_walk()
3635 if (pivots[offset] >= mas->index) in mtree_lookup_walk()
3640 next = mt_slot(mas->tree, slots, offset); in mtree_lookup_walk()
3648 mas_reset(mas); in mtree_lookup_walk()
3661 static inline void mas_new_root(struct ma_state *mas, void *entry) in mas_new_root() argument
3663 struct maple_enode *root = mas_root_locked(mas); in mas_new_root()
3669 WARN_ON_ONCE(mas->index || mas->last != ULONG_MAX); in mas_new_root()
3672 mas->depth = 0; in mas_new_root()
3673 mas_set_height(mas); in mas_new_root()
3674 rcu_assign_pointer(mas->tree->ma_root, entry); in mas_new_root()
3675 mas->status = ma_start; in mas_new_root()
3679 node = mas_pop_node(mas); in mas_new_root()
3682 node->parent = ma_parent_ptr(mas_tree_parent(mas)); in mas_new_root()
3683 mas->node = mt_mk_node(node, type); in mas_new_root()
3684 mas->status = ma_active; in mas_new_root()
3686 pivots[0] = mas->last; in mas_new_root()
3687 mas->depth = 1; in mas_new_root()
3688 mas_set_height(mas); in mas_new_root()
3689 rcu_assign_pointer(mas->tree->ma_root, mte_mk_root(mas->node)); in mas_new_root()
3693 mte_destroy_walk(root, mas->tree); in mas_new_root()
3708 struct ma_state *mas; in mas_wr_spanning_store() local
3729 mas = wr_mas->mas; in mas_wr_spanning_store()
3730 trace_ma_op(__func__, mas); in mas_wr_spanning_store()
3732 if (unlikely(!mas->index && mas->last == ULONG_MAX)) in mas_wr_spanning_store()
3733 return mas_new_root(mas, wr_mas->entry); in mas_wr_spanning_store()
3738 height = mas_mt_height(mas); in mas_wr_spanning_store()
3745 r_mas = *mas; in mas_wr_spanning_store()
3752 r_mas.last = r_mas.index = mas->last; in mas_wr_spanning_store()
3755 l_mas = *mas; in mas_wr_spanning_store()
3760 mas->offset = l_mas.offset; in mas_wr_spanning_store()
3761 mas->index = l_mas.index; in mas_wr_spanning_store()
3762 mas->last = l_mas.last = r_mas.last; in mas_wr_spanning_store()
3767 mas_set_range(mas, 0, ULONG_MAX); in mas_wr_spanning_store()
3768 return mas_new_root(mas, wr_mas->entry); in mas_wr_spanning_store()
3782 l_mas.index = l_mas.last = mas->index; in mas_wr_spanning_store()
3788 return mas_spanning_rebalance(mas, &mast, height + 1); in mas_wr_spanning_store()
3800 struct ma_state *mas = wr_mas->mas; in mas_wr_node_store() local
3806 bool in_rcu = mt_in_rcu(mas->tree); in mas_wr_node_store()
3808 if (mas->last == wr_mas->end_piv) in mas_wr_node_store()
3811 mas_bulk_rebalance(mas, mas->end, wr_mas->type); in mas_wr_node_store()
3815 newnode = mas_pop_node(mas); in mas_wr_node_store()
3821 newnode->parent = mas_mn(mas)->parent; in mas_wr_node_store()
3825 memcpy(dst_pivots, wr_mas->pivots, sizeof(unsigned long) * mas->offset); in mas_wr_node_store()
3826 memcpy(dst_slots, wr_mas->slots, sizeof(void *) * mas->offset); in mas_wr_node_store()
3829 if (wr_mas->r_min < mas->index) { in mas_wr_node_store()
3830 rcu_assign_pointer(dst_slots[mas->offset], wr_mas->content); in mas_wr_node_store()
3831 dst_pivots[mas->offset++] = mas->index - 1; in mas_wr_node_store()
3835 if (mas->offset < node_pivots) in mas_wr_node_store()
3836 dst_pivots[mas->offset] = mas->last; in mas_wr_node_store()
3837 rcu_assign_pointer(dst_slots[mas->offset], wr_mas->entry); in mas_wr_node_store()
3843 if (offset_end > mas->end) in mas_wr_node_store()
3846 dst_offset = mas->offset + 1; in mas_wr_node_store()
3848 copy_size = mas->end - offset_end + 1; in mas_wr_node_store()
3855 dst_pivots[new_end] = mas->max; in mas_wr_node_store()
3860 struct maple_enode *old_enode = mas->node; in mas_wr_node_store()
3862 mas->node = mt_mk_node(newnode, wr_mas->type); in mas_wr_node_store()
3863 mas_replace_node(mas, old_enode); in mas_wr_node_store()
3867 trace_ma_write(__func__, mas, 0, wr_mas->entry); in mas_wr_node_store()
3868 mas_update_gap(mas); in mas_wr_node_store()
3869 mas->end = new_end; in mas_wr_node_store()
3879 struct ma_state *mas = wr_mas->mas; in mas_wr_slot_store() local
3880 unsigned char offset = mas->offset; in mas_wr_slot_store()
3884 gap |= !mt_slot_locked(mas->tree, slots, offset); in mas_wr_slot_store()
3885 gap |= !mt_slot_locked(mas->tree, slots, offset + 1); in mas_wr_slot_store()
3888 if (mas->index == wr_mas->r_min) { in mas_wr_slot_store()
3891 wr_mas->pivots[offset] = mas->last; in mas_wr_slot_store()
3895 wr_mas->pivots[offset] = mas->index - 1; in mas_wr_slot_store()
3896 mas->offset++; /* Keep mas accurate. */ in mas_wr_slot_store()
3899 WARN_ON_ONCE(mt_in_rcu(mas->tree)); in mas_wr_slot_store()
3904 gap |= !mt_slot_locked(mas->tree, slots, offset + 2); in mas_wr_slot_store()
3906 wr_mas->pivots[offset] = mas->index - 1; in mas_wr_slot_store()
3907 wr_mas->pivots[offset + 1] = mas->last; in mas_wr_slot_store()
3908 mas->offset++; /* Keep mas accurate. */ in mas_wr_slot_store()
3911 trace_ma_write(__func__, mas, 0, wr_mas->entry); in mas_wr_slot_store()
3917 mas_update_gap(mas); in mas_wr_slot_store()
3924 struct ma_state *mas = wr_mas->mas; in mas_wr_extend_null() local
3928 mas->last = wr_mas->end_piv; in mas_wr_extend_null()
3931 if ((mas->last == wr_mas->end_piv) && in mas_wr_extend_null()
3932 (mas->end != wr_mas->offset_end) && in mas_wr_extend_null()
3935 if (wr_mas->offset_end == mas->end) in mas_wr_extend_null()
3936 mas->last = mas->max; in mas_wr_extend_null()
3938 mas->last = wr_mas->pivots[wr_mas->offset_end]; in mas_wr_extend_null()
3939 wr_mas->end_piv = mas->last; in mas_wr_extend_null()
3945 mas->index = wr_mas->r_min; in mas_wr_extend_null()
3948 if (mas->index == wr_mas->r_min && mas->offset && in mas_wr_extend_null()
3949 !wr_mas->slots[mas->offset - 1]) { in mas_wr_extend_null()
3950 mas->offset--; in mas_wr_extend_null()
3951 wr_mas->r_min = mas->index = in mas_wr_extend_null()
3952 mas_safe_min(mas, wr_mas->pivots, mas->offset); in mas_wr_extend_null()
3953 wr_mas->r_max = wr_mas->pivots[mas->offset]; in mas_wr_extend_null()
3960 while ((wr_mas->offset_end < wr_mas->mas->end) && in mas_wr_end_piv()
3961 (wr_mas->mas->last > wr_mas->pivots[wr_mas->offset_end])) in mas_wr_end_piv()
3964 if (wr_mas->offset_end < wr_mas->mas->end) in mas_wr_end_piv()
3967 wr_mas->end_piv = wr_mas->mas->max; in mas_wr_end_piv()
3972 struct ma_state *mas = wr_mas->mas; in mas_wr_new_end() local
3973 unsigned char new_end = mas->end + 2; in mas_wr_new_end()
3975 new_end -= wr_mas->offset_end - mas->offset; in mas_wr_new_end()
3976 if (wr_mas->r_min == mas->index) in mas_wr_new_end()
3979 if (wr_mas->end_piv == mas->last) in mas_wr_new_end()
3997 struct ma_state *mas = wr_mas->mas; in mas_wr_append() local
3999 unsigned char end = mas->end; in mas_wr_append()
4008 if (mas->last == wr_mas->r_max) { in mas_wr_append()
4011 wr_mas->pivots[end] = mas->index - 1; in mas_wr_append()
4012 mas->offset = new_end; in mas_wr_append()
4016 wr_mas->pivots[end] = mas->last; in mas_wr_append()
4022 wr_mas->pivots[end + 1] = mas->last; in mas_wr_append()
4024 wr_mas->pivots[end] = mas->index - 1; in mas_wr_append()
4025 mas->offset = end + 1; in mas_wr_append()
4029 mas_update_gap(mas); in mas_wr_append()
4031 mas->end = new_end; in mas_wr_append()
4032 trace_ma_write(__func__, mas, new_end, wr_mas->entry); in mas_wr_append()
4046 trace_ma_write(__func__, wr_mas->mas, 0, wr_mas->entry); in mas_wr_bnode()
4058 struct ma_state *mas = wr_mas->mas; in mas_wr_store_entry() local
4061 switch (mas->store_type) { in mas_wr_store_entry()
4063 MT_BUG_ON(mas->tree, 1); in mas_wr_store_entry()
4066 mas_new_root(mas, wr_mas->entry); in mas_wr_store_entry()
4069 mas_store_root(mas, wr_mas->entry); in mas_wr_store_entry()
4072 rcu_assign_pointer(wr_mas->slots[mas->offset], wr_mas->entry); in mas_wr_store_entry()
4074 mas_update_gap(mas); in mas_wr_store_entry()
4099 struct ma_state *mas = wr_mas->mas; in mas_wr_prealloc_setup() local
4101 if (!mas_is_active(mas)) { in mas_wr_prealloc_setup()
4102 if (mas_is_start(mas)) in mas_wr_prealloc_setup()
4105 if (unlikely(mas_is_paused(mas))) in mas_wr_prealloc_setup()
4108 if (unlikely(mas_is_none(mas))) in mas_wr_prealloc_setup()
4111 if (unlikely(mas_is_overflow(mas))) in mas_wr_prealloc_setup()
4114 if (unlikely(mas_is_underflow(mas))) in mas_wr_prealloc_setup()
4123 if (mas->last > mas->max) in mas_wr_prealloc_setup()
4129 if (mte_is_leaf(mas->node) && mas->last == mas->max) in mas_wr_prealloc_setup()
4135 mas_reset(mas); in mas_wr_prealloc_setup()
4137 wr_mas->content = mas_start(mas); in mas_wr_prealloc_setup()
4148 static inline int mas_prealloc_calc(struct ma_state *mas, void *entry) in mas_prealloc_calc() argument
4150 int ret = mas_mt_height(mas) * 3 + 1; in mas_prealloc_calc()
4152 switch (mas->store_type) { in mas_prealloc_calc()
4160 if (likely((mas->last != 0) || (mas->index != 0))) in mas_prealloc_calc()
4168 ret = mas_mt_height(mas) * 3 + 1; in mas_prealloc_calc()
4171 ret = mas_mt_height(mas) * 2 + 1; in mas_prealloc_calc()
4174 ret = mas_mt_height(mas) * 2 - 1; in mas_prealloc_calc()
4177 ret = mt_in_rcu(mas->tree) ? 1 : 0; in mas_prealloc_calc()
4197 struct ma_state *mas = wr_mas->mas; in mas_wr_store_type() local
4200 if (unlikely(mas_is_none(mas) || mas_is_ptr(mas))) in mas_wr_store_type()
4211 if ((wr_mas->r_min == mas->index) && (wr_mas->r_max == mas->last)) in mas_wr_store_type()
4214 if (unlikely(!mas->index && mas->last == ULONG_MAX)) in mas_wr_store_type()
4220 if (!mte_is_root(mas->node) && !(mas->mas_flags & MA_STATE_BULK)) in mas_wr_store_type()
4228 if (!mt_in_rcu(mas->tree) && (mas->offset == mas->end)) in mas_wr_store_type()
4231 if ((new_end == mas->end) && (!mt_in_rcu(mas->tree) || in mas_wr_store_type()
4232 (wr_mas->offset_end - mas->offset == 1))) in mas_wr_store_type()
4246 struct ma_state *mas = wr_mas->mas; in mas_wr_preallocate() local
4250 mas->store_type = mas_wr_store_type(wr_mas); in mas_wr_preallocate()
4251 request = mas_prealloc_calc(mas, entry); in mas_wr_preallocate()
4255 mas_node_count(mas, request); in mas_wr_preallocate()
4266 static inline void *mas_insert(struct ma_state *mas, void *entry) in mas_insert() argument
4268 MA_WR_STATE(wr_mas, mas, entry); in mas_insert()
4284 wr_mas.content = mas_start(mas); in mas_insert()
4289 if (mas_is_err(mas)) in mas_insert()
4293 if (mas->store_type == wr_spanning_store) in mas_insert()
4297 if (mas->store_type != wr_new_root && mas->store_type != wr_store_root) { in mas_insert()
4298 wr_mas.offset_end = mas->offset; in mas_insert()
4301 if (wr_mas.content || (mas->last > wr_mas.r_max)) in mas_insert()
4309 mas_set_err(mas, -EEXIST); in mas_insert()
4328 int mas_alloc_cyclic(struct ma_state *mas, unsigned long *startp, in mas_alloc_cyclic() argument
4336 ret = mas_empty_area(mas, range_lo, range_hi, 1); in mas_alloc_cyclic()
4337 if ((mas->tree->ma_flags & MT_FLAGS_ALLOC_WRAPPED) && ret == 0) { in mas_alloc_cyclic()
4338 mas->tree->ma_flags &= ~MT_FLAGS_ALLOC_WRAPPED; in mas_alloc_cyclic()
4342 mas_reset(mas); in mas_alloc_cyclic()
4343 ret = mas_empty_area(mas, min, range_hi, 1); in mas_alloc_cyclic()
4351 mas_insert(mas, entry); in mas_alloc_cyclic()
4352 } while (mas_nomem(mas, gfp)); in mas_alloc_cyclic()
4353 if (mas_is_err(mas)) in mas_alloc_cyclic()
4354 return xa_err(mas->node); in mas_alloc_cyclic()
4356 *startp = mas->index; in mas_alloc_cyclic()
4359 mas->tree->ma_flags |= MT_FLAGS_ALLOC_WRAPPED; in mas_alloc_cyclic()
4361 mas_destroy(mas); in mas_alloc_cyclic()
4366 static __always_inline void mas_rewalk(struct ma_state *mas, unsigned long index) in mas_rewalk() argument
4369 mas_set(mas, index); in mas_rewalk()
4370 mas_state_walk(mas); in mas_rewalk()
4371 if (mas_is_start(mas)) in mas_rewalk()
4375 static __always_inline bool mas_rewalk_if_dead(struct ma_state *mas, in mas_rewalk_if_dead() argument
4379 mas_rewalk(mas, index); in mas_rewalk_if_dead()
4396 static int mas_prev_node(struct ma_state *mas, unsigned long min) in mas_prev_node() argument
4405 node = mas_mn(mas); in mas_prev_node()
4406 if (!mas->min) in mas_prev_node()
4409 max = mas->min - 1; in mas_prev_node()
4419 if (unlikely(mas_ascend(mas))) in mas_prev_node()
4421 offset = mas->offset; in mas_prev_node()
4423 node = mas_mn(mas); in mas_prev_node()
4427 mt = mte_node_type(mas->node); in mas_prev_node()
4431 mas->node = mas_slot(mas, slots, offset); in mas_prev_node()
4435 mt = mte_node_type(mas->node); in mas_prev_node()
4436 node = mas_mn(mas); in mas_prev_node()
4444 mas->node = mas_slot(mas, slots, offset); in mas_prev_node()
4450 mas->min = pivots[offset - 1] + 1; in mas_prev_node()
4451 mas->max = max; in mas_prev_node()
4452 mas->offset = mas_data_end(mas); in mas_prev_node()
4453 if (unlikely(mte_dead_node(mas->node))) in mas_prev_node()
4456 mas->end = mas->offset; in mas_prev_node()
4463 mas->status = ma_underflow; in mas_prev_node()
4476 static void *mas_prev_slot(struct ma_state *mas, unsigned long min, bool empty) in mas_prev_slot() argument
4484 unsigned long save_point = mas->index; in mas_prev_slot()
4487 node = mas_mn(mas); in mas_prev_slot()
4488 type = mte_node_type(mas->node); in mas_prev_slot()
4490 if (unlikely(mas_rewalk_if_dead(mas, node, save_point))) in mas_prev_slot()
4493 if (mas->min <= min) { in mas_prev_slot()
4494 pivot = mas_safe_min(mas, pivots, mas->offset); in mas_prev_slot()
4496 if (unlikely(mas_rewalk_if_dead(mas, node, save_point))) in mas_prev_slot()
4504 if (likely(mas->offset)) { in mas_prev_slot()
4505 mas->offset--; in mas_prev_slot()
4506 mas->last = mas->index - 1; in mas_prev_slot()
4507 mas->index = mas_safe_min(mas, pivots, mas->offset); in mas_prev_slot()
4509 if (mas->index <= min) in mas_prev_slot()
4512 if (mas_prev_node(mas, min)) { in mas_prev_slot()
4513 mas_rewalk(mas, save_point); in mas_prev_slot()
4517 if (WARN_ON_ONCE(mas_is_underflow(mas))) in mas_prev_slot()
4520 mas->last = mas->max; in mas_prev_slot()
4521 node = mas_mn(mas); in mas_prev_slot()
4522 type = mte_node_type(mas->node); in mas_prev_slot()
4524 mas->index = pivots[mas->offset - 1] + 1; in mas_prev_slot()
4528 entry = mas_slot(mas, slots, mas->offset); in mas_prev_slot()
4529 if (unlikely(mas_rewalk_if_dead(mas, node, save_point))) in mas_prev_slot()
4537 if (mas->index <= min) { in mas_prev_slot()
4538 mas->status = ma_underflow; in mas_prev_slot()
4548 mas->status = ma_underflow; in mas_prev_slot()
4562 static int mas_next_node(struct ma_state *mas, struct maple_node *node, in mas_next_node() argument
4574 if (mas->max >= max) in mas_next_node()
4577 min = mas->max + 1; in mas_next_node()
4584 if (unlikely(mas_ascend(mas))) in mas_next_node()
4588 node = mas_mn(mas); in mas_next_node()
4589 mt = mte_node_type(mas->node); in mas_next_node()
4591 node_end = ma_data_end(node, mt, pivots, mas->max); in mas_next_node()
4595 } while (unlikely(mas->offset == node_end)); in mas_next_node()
4598 mas->offset++; in mas_next_node()
4599 enode = mas_slot(mas, slots, mas->offset); in mas_next_node()
4604 mas->offset = 0; in mas_next_node()
4608 mas->node = enode; in mas_next_node()
4609 node = mas_mn(mas); in mas_next_node()
4610 mt = mte_node_type(mas->node); in mas_next_node()
4612 enode = mas_slot(mas, slots, 0); in mas_next_node()
4617 if (!mas->offset) in mas_next_node()
4620 mas->max = mas_safe_pivot(mas, pivots, mas->offset, mt); in mas_next_node()
4624 mas->end = ma_data_end(tmp, mt, pivots, mas->max); in mas_next_node()
4628 mas->node = enode; in mas_next_node()
4629 mas->min = min; in mas_next_node()
4636 mas->status = ma_overflow; in mas_next_node()
4649 static void *mas_next_slot(struct ma_state *mas, unsigned long max, bool empty) in mas_next_slot() argument
4656 unsigned long save_point = mas->last; in mas_next_slot()
4660 node = mas_mn(mas); in mas_next_slot()
4661 type = mte_node_type(mas->node); in mas_next_slot()
4663 if (unlikely(mas_rewalk_if_dead(mas, node, save_point))) in mas_next_slot()
4666 if (mas->max >= max) { in mas_next_slot()
4667 if (likely(mas->offset < mas->end)) in mas_next_slot()
4668 pivot = pivots[mas->offset]; in mas_next_slot()
4670 pivot = mas->max; in mas_next_slot()
4672 if (unlikely(mas_rewalk_if_dead(mas, node, save_point))) in mas_next_slot()
4676 mas->status = ma_overflow; in mas_next_slot()
4681 if (likely(mas->offset < mas->end)) { in mas_next_slot()
4682 mas->index = pivots[mas->offset] + 1; in mas_next_slot()
4684 mas->offset++; in mas_next_slot()
4685 if (likely(mas->offset < mas->end)) in mas_next_slot()
4686 mas->last = pivots[mas->offset]; in mas_next_slot()
4688 mas->last = mas->max; in mas_next_slot()
4690 if (mas->last >= max) { in mas_next_slot()
4691 mas->status = ma_overflow; in mas_next_slot()
4695 if (mas_next_node(mas, node, max)) { in mas_next_slot()
4696 mas_rewalk(mas, save_point); in mas_next_slot()
4700 if (WARN_ON_ONCE(mas_is_overflow(mas))) in mas_next_slot()
4703 mas->offset = 0; in mas_next_slot()
4704 mas->index = mas->min; in mas_next_slot()
4705 node = mas_mn(mas); in mas_next_slot()
4706 type = mte_node_type(mas->node); in mas_next_slot()
4708 mas->last = pivots[0]; in mas_next_slot()
4712 entry = mt_slot(mas->tree, slots, mas->offset); in mas_next_slot()
4713 if (unlikely(mas_rewalk_if_dead(mas, node, save_point))) in mas_next_slot()
4721 if (mas->last >= max) { in mas_next_slot()
4722 mas->status = ma_overflow; in mas_next_slot()
4726 mas->index = mas->last + 1; in mas_next_slot()
4742 static bool mas_rev_awalk(struct ma_state *mas, unsigned long size, in mas_rev_awalk() argument
4745 enum maple_type type = mte_node_type(mas->node); in mas_rev_awalk()
4746 struct maple_node *node = mas_mn(mas); in mas_rev_awalk()
4753 if (unlikely(mas_is_err(mas))) in mas_rev_awalk()
4758 mas->offset = (unsigned char)(mas->index - mas->min); in mas_rev_awalk()
4765 offset = mas->offset; in mas_rev_awalk()
4766 min = mas_safe_min(mas, pivots, offset); in mas_rev_awalk()
4768 while (mas->last < min) in mas_rev_awalk()
4769 min = mas_safe_min(mas, pivots, --offset); in mas_rev_awalk()
4771 max = mas_safe_pivot(mas, pivots, offset, type); in mas_rev_awalk()
4772 while (mas->index <= max) { in mas_rev_awalk()
4776 else if (!mas_slot(mas, slots, offset)) in mas_rev_awalk()
4780 if ((size <= gap) && (size <= mas->last - min + 1)) in mas_rev_awalk()
4790 min = mas_safe_min(mas, pivots, offset); in mas_rev_awalk()
4800 min = mas_safe_min(mas, pivots, offset); in mas_rev_awalk()
4803 if (unlikely((mas->index > max) || (size - 1 > max - mas->index))) in mas_rev_awalk()
4807 mas->offset = offset; in mas_rev_awalk()
4814 mas->node = mas_slot(mas, slots, offset); in mas_rev_awalk()
4815 mas->min = min; in mas_rev_awalk()
4816 mas->max = max; in mas_rev_awalk()
4817 mas->offset = mas_data_end(mas); in mas_rev_awalk()
4821 if (!mte_is_root(mas->node)) in mas_rev_awalk()
4825 mas_set_err(mas, -EBUSY); in mas_rev_awalk()
4829 static inline bool mas_anode_descend(struct ma_state *mas, unsigned long size) in mas_anode_descend() argument
4831 enum maple_type type = mte_node_type(mas->node); in mas_anode_descend()
4840 mas->offset = (unsigned char)(mas->index - mas->min); in mas_anode_descend()
4844 node = mas_mn(mas); in mas_anode_descend()
4848 offset = mas->offset; in mas_anode_descend()
4849 min = mas_safe_min(mas, pivots, offset); in mas_anode_descend()
4850 data_end = ma_data_end(node, type, pivots, mas->max); in mas_anode_descend()
4852 pivot = mas_safe_pivot(mas, pivots, offset, type); in mas_anode_descend()
4855 if (mas->index > pivot) in mas_anode_descend()
4860 else if (!mas_slot(mas, slots, offset)) in mas_anode_descend()
4861 gap = min(pivot, mas->last) - max(mas->index, min) + 1; in mas_anode_descend()
4871 mas->node = mas_slot(mas, slots, offset); in mas_anode_descend()
4872 mas->min = min; in mas_anode_descend()
4873 mas->max = pivot; in mas_anode_descend()
4879 if (mas->last <= pivot) { in mas_anode_descend()
4880 mas_set_err(mas, -EBUSY); in mas_anode_descend()
4885 mas->offset = offset; in mas_anode_descend()
4898 void *mas_walk(struct ma_state *mas) in mas_walk() argument
4902 if (!mas_is_active(mas) || !mas_is_start(mas)) in mas_walk()
4903 mas->status = ma_start; in mas_walk()
4905 entry = mas_state_walk(mas); in mas_walk()
4906 if (mas_is_start(mas)) { in mas_walk()
4908 } else if (mas_is_none(mas)) { in mas_walk()
4909 mas->index = 0; in mas_walk()
4910 mas->last = ULONG_MAX; in mas_walk()
4911 } else if (mas_is_ptr(mas)) { in mas_walk()
4912 if (!mas->index) { in mas_walk()
4913 mas->last = 0; in mas_walk()
4917 mas->index = 1; in mas_walk()
4918 mas->last = ULONG_MAX; in mas_walk()
4919 mas->status = ma_none; in mas_walk()
4927 static inline bool mas_rewind_node(struct ma_state *mas) in mas_rewind_node() argument
4932 if (mte_is_root(mas->node)) { in mas_rewind_node()
4933 slot = mas->offset; in mas_rewind_node()
4937 mas_ascend(mas); in mas_rewind_node()
4938 slot = mas->offset; in mas_rewind_node()
4942 mas->offset = --slot; in mas_rewind_node()
4952 static inline bool mas_skip_node(struct ma_state *mas) in mas_skip_node() argument
4954 if (mas_is_err(mas)) in mas_skip_node()
4958 if (mte_is_root(mas->node)) { in mas_skip_node()
4959 if (mas->offset >= mas_data_end(mas)) { in mas_skip_node()
4960 mas_set_err(mas, -EBUSY); in mas_skip_node()
4964 mas_ascend(mas); in mas_skip_node()
4966 } while (mas->offset >= mas_data_end(mas)); in mas_skip_node()
4968 mas->offset++; in mas_skip_node()
4980 static inline void mas_awalk(struct ma_state *mas, unsigned long size) in mas_awalk() argument
4991 while (!mas_is_err(mas) && !mas_anode_descend(mas, size)) { in mas_awalk()
4992 if (last == mas->node) in mas_awalk()
4993 mas_skip_node(mas); in mas_awalk()
4995 last = mas->node; in mas_awalk()
5008 static inline int mas_sparse_area(struct ma_state *mas, unsigned long min, in mas_sparse_area() argument
5011 if (!unlikely(mas_is_none(mas)) && min == 0) { in mas_sparse_area()
5023 mas->index = min; in mas_sparse_area()
5024 mas->last = min + size - 1; in mas_sparse_area()
5026 mas->last = max; in mas_sparse_area()
5027 mas->index = max - size + 1; in mas_sparse_area()
5040 int mas_empty_area(struct ma_state *mas, unsigned long min, in mas_empty_area() argument
5054 if (mas_is_start(mas)) in mas_empty_area()
5055 mas_start(mas); in mas_empty_area()
5056 else if (mas->offset >= 2) in mas_empty_area()
5057 mas->offset -= 2; in mas_empty_area()
5058 else if (!mas_skip_node(mas)) in mas_empty_area()
5062 if (mas_is_none(mas) || mas_is_ptr(mas)) in mas_empty_area()
5063 return mas_sparse_area(mas, min, max, size, true); in mas_empty_area()
5066 mas->index = min; in mas_empty_area()
5067 mas->last = max; in mas_empty_area()
5068 mas_awalk(mas, size); in mas_empty_area()
5070 if (unlikely(mas_is_err(mas))) in mas_empty_area()
5071 return xa_err(mas->node); in mas_empty_area()
5073 offset = mas->offset; in mas_empty_area()
5074 node = mas_mn(mas); in mas_empty_area()
5075 mt = mte_node_type(mas->node); in mas_empty_area()
5077 min = mas_safe_min(mas, pivots, offset); in mas_empty_area()
5078 if (mas->index < min) in mas_empty_area()
5079 mas->index = min; in mas_empty_area()
5080 mas->last = mas->index + size - 1; in mas_empty_area()
5081 mas->end = ma_data_end(node, mt, pivots, mas->max); in mas_empty_area()
5094 int mas_empty_area_rev(struct ma_state *mas, unsigned long min, in mas_empty_area_rev() argument
5097 struct maple_enode *last = mas->node; in mas_empty_area_rev()
5105 if (mas_is_start(mas)) in mas_empty_area_rev()
5106 mas_start(mas); in mas_empty_area_rev()
5107 else if ((mas->offset < 2) && (!mas_rewind_node(mas))) in mas_empty_area_rev()
5110 if (unlikely(mas_is_none(mas) || mas_is_ptr(mas))) in mas_empty_area_rev()
5111 return mas_sparse_area(mas, min, max, size, false); in mas_empty_area_rev()
5112 else if (mas->offset >= 2) in mas_empty_area_rev()
5113 mas->offset -= 2; in mas_empty_area_rev()
5115 mas->offset = mas_data_end(mas); in mas_empty_area_rev()
5119 mas->index = min; in mas_empty_area_rev()
5120 mas->last = max; in mas_empty_area_rev()
5122 while (!mas_rev_awalk(mas, size, &min, &max)) { in mas_empty_area_rev()
5123 if (last == mas->node) { in mas_empty_area_rev()
5124 if (!mas_rewind_node(mas)) in mas_empty_area_rev()
5127 last = mas->node; in mas_empty_area_rev()
5131 if (mas_is_err(mas)) in mas_empty_area_rev()
5132 return xa_err(mas->node); in mas_empty_area_rev()
5134 if (unlikely(mas->offset == MAPLE_NODE_SLOTS)) in mas_empty_area_rev()
5138 if (max < mas->last) in mas_empty_area_rev()
5139 mas->last = max; in mas_empty_area_rev()
5141 mas->index = mas->last - size + 1; in mas_empty_area_rev()
5142 mas->end = mas_data_end(mas); in mas_empty_area_rev()
5368 void *mas_store(struct ma_state *mas, void *entry) in mas_store() argument
5371 MA_WR_STATE(wr_mas, mas, entry); in mas_store()
5373 trace_ma_write(__func__, mas, 0, entry); in mas_store()
5375 if (MAS_WARN_ON(mas, mas->index > mas->last)) in mas_store()
5376 pr_err("Error %lX > %lX " PTR_FMT "\n", mas->index, mas->last, in mas_store()
5379 if (mas->index > mas->last) { in mas_store()
5380 mas_set_err(mas, -EINVAL); in mas_store()
5393 mas->store_type = mas_wr_store_type(&wr_mas); in mas_store()
5394 if (mas->mas_flags & MA_STATE_PREALLOC) { in mas_store()
5396 MAS_WR_BUG_ON(&wr_mas, mas_is_err(mas)); in mas_store()
5400 request = mas_prealloc_calc(mas, entry); in mas_store()
5404 mas_node_count(mas, request); in mas_store()
5405 if (mas_is_err(mas)) in mas_store()
5410 mas_destroy(mas); in mas_store()
5424 int mas_store_gfp(struct ma_state *mas, void *entry, gfp_t gfp) in mas_store_gfp() argument
5426 unsigned long index = mas->index; in mas_store_gfp()
5427 unsigned long last = mas->last; in mas_store_gfp()
5428 MA_WR_STATE(wr_mas, mas, entry); in mas_store_gfp()
5433 if (unlikely(mas_nomem(mas, gfp))) { in mas_store_gfp()
5435 __mas_set_range(mas, index, last); in mas_store_gfp()
5439 if (mas_is_err(mas)) { in mas_store_gfp()
5440 ret = xa_err(mas->node); in mas_store_gfp()
5446 mas_destroy(mas); in mas_store_gfp()
5457 void mas_store_prealloc(struct ma_state *mas, void *entry) in mas_store_prealloc() argument
5459 MA_WR_STATE(wr_mas, mas, entry); in mas_store_prealloc()
5461 if (mas->store_type == wr_store_root) { in mas_store_prealloc()
5467 if (mas->store_type != wr_spanning_store) { in mas_store_prealloc()
5469 wr_mas.content = mas_slot_locked(mas, wr_mas.slots, mas->offset); in mas_store_prealloc()
5474 trace_ma_write(__func__, mas, 0, entry); in mas_store_prealloc()
5476 MAS_WR_BUG_ON(&wr_mas, mas_is_err(mas)); in mas_store_prealloc()
5477 mas_destroy(mas); in mas_store_prealloc()
5489 int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp) in mas_preallocate() argument
5491 MA_WR_STATE(wr_mas, mas, entry); in mas_preallocate()
5496 mas->store_type = mas_wr_store_type(&wr_mas); in mas_preallocate()
5497 request = mas_prealloc_calc(mas, entry); in mas_preallocate()
5501 mas_node_count_gfp(mas, request, gfp); in mas_preallocate()
5502 if (mas_is_err(mas)) { in mas_preallocate()
5503 mas_set_alloc_req(mas, 0); in mas_preallocate()
5504 ret = xa_err(mas->node); in mas_preallocate()
5505 mas_destroy(mas); in mas_preallocate()
5506 mas_reset(mas); in mas_preallocate()
5510 mas->mas_flags |= MA_STATE_PREALLOC; in mas_preallocate()
5523 void mas_destroy(struct ma_state *mas) in mas_destroy() argument
5534 if (mas->mas_flags & MA_STATE_REBALANCE) { in mas_destroy()
5536 if (mas_is_err(mas)) in mas_destroy()
5537 mas_reset(mas); in mas_destroy()
5538 mas_start(mas); in mas_destroy()
5539 mtree_range_walk(mas); in mas_destroy()
5540 end = mas->end + 1; in mas_destroy()
5541 if (end < mt_min_slot_count(mas->node) - 1) in mas_destroy()
5542 mas_destroy_rebalance(mas, end); in mas_destroy()
5544 mas->mas_flags &= ~MA_STATE_REBALANCE; in mas_destroy()
5546 mas->mas_flags &= ~(MA_STATE_BULK|MA_STATE_PREALLOC); in mas_destroy()
5548 total = mas_allocated(mas); in mas_destroy()
5550 node = mas->alloc; in mas_destroy()
5551 mas->alloc = node->slot[0]; in mas_destroy()
5562 mas->alloc = NULL; in mas_destroy()
5578 int mas_expected_entries(struct ma_state *mas, unsigned long nr_entries) in mas_expected_entries() argument
5581 struct maple_enode *enode = mas->node; in mas_expected_entries()
5596 mas->mas_flags |= MA_STATE_BULK; in mas_expected_entries()
5604 if (!mt_is_alloc(mas->tree)) in mas_expected_entries()
5612 mas_node_count_gfp(mas, nr_nodes + 3, GFP_KERNEL); in mas_expected_entries()
5615 mas->mas_flags |= MA_STATE_PREALLOC; in mas_expected_entries()
5617 if (!mas_is_err(mas)) in mas_expected_entries()
5620 ret = xa_err(mas->node); in mas_expected_entries()
5621 mas->node = enode; in mas_expected_entries()
5622 mas_destroy(mas); in mas_expected_entries()
5628 static bool mas_next_setup(struct ma_state *mas, unsigned long max, in mas_next_setup() argument
5631 bool was_none = mas_is_none(mas); in mas_next_setup()
5633 if (unlikely(mas->last >= max)) { in mas_next_setup()
5634 mas->status = ma_overflow; in mas_next_setup()
5638 switch (mas->status) { in mas_next_setup()
5644 mas->status = ma_start; in mas_next_setup()
5647 mas_walk(mas); /* Retries on dead nodes handled by mas_walk */ in mas_next_setup()
5651 mas->status = ma_active; in mas_next_setup()
5655 mas->status = ma_active; in mas_next_setup()
5656 *entry = mas_walk(mas); in mas_next_setup()
5666 if (likely(mas_is_active(mas))) /* Fast path */ in mas_next_setup()
5669 if (mas_is_ptr(mas)) { in mas_next_setup()
5671 if (was_none && mas->index == 0) { in mas_next_setup()
5672 mas->index = mas->last = 0; in mas_next_setup()
5675 mas->index = 1; in mas_next_setup()
5676 mas->last = ULONG_MAX; in mas_next_setup()
5677 mas->status = ma_none; in mas_next_setup()
5681 if (mas_is_none(mas)) in mas_next_setup()
5698 void *mas_next(struct ma_state *mas, unsigned long max) in mas_next() argument
5702 if (mas_next_setup(mas, max, &entry)) in mas_next()
5706 return mas_next_slot(mas, max, false); in mas_next()
5721 void *mas_next_range(struct ma_state *mas, unsigned long max) in mas_next_range() argument
5725 if (mas_next_setup(mas, max, &entry)) in mas_next_range()
5729 return mas_next_slot(mas, max, true); in mas_next_range()
5748 MA_STATE(mas, mt, index, index); in mt_next()
5751 entry = mas_next(&mas, max); in mt_next()
5757 static bool mas_prev_setup(struct ma_state *mas, unsigned long min, void **entry) in mas_prev_setup() argument
5759 if (unlikely(mas->index <= min)) { in mas_prev_setup()
5760 mas->status = ma_underflow; in mas_prev_setup()
5764 switch (mas->status) { in mas_prev_setup()
5772 mas->status = ma_start; in mas_prev_setup()
5776 mas->status = ma_active; in mas_prev_setup()
5780 mas->status = ma_active; in mas_prev_setup()
5781 *entry = mas_walk(mas); in mas_prev_setup()
5791 if (mas_is_start(mas)) in mas_prev_setup()
5792 mas_walk(mas); in mas_prev_setup()
5794 if (unlikely(mas_is_ptr(mas))) { in mas_prev_setup()
5795 if (!mas->index) { in mas_prev_setup()
5796 mas->status = ma_none; in mas_prev_setup()
5799 mas->index = mas->last = 0; in mas_prev_setup()
5800 *entry = mas_root(mas); in mas_prev_setup()
5804 if (mas_is_none(mas)) { in mas_prev_setup()
5805 if (mas->index) { in mas_prev_setup()
5807 mas->index = mas->last = 0; in mas_prev_setup()
5808 mas->status = ma_root; in mas_prev_setup()
5809 *entry = mas_root(mas); in mas_prev_setup()
5829 void *mas_prev(struct ma_state *mas, unsigned long min) in mas_prev() argument
5833 if (mas_prev_setup(mas, min, &entry)) in mas_prev()
5836 return mas_prev_slot(mas, min, false); in mas_prev()
5852 void *mas_prev_range(struct ma_state *mas, unsigned long min) in mas_prev_range() argument
5856 if (mas_prev_setup(mas, min, &entry)) in mas_prev_range()
5859 return mas_prev_slot(mas, min, true); in mas_prev_range()
5878 MA_STATE(mas, mt, index, index); in mt_prev()
5881 entry = mas_prev(&mas, min); in mt_prev()
5900 void mas_pause(struct ma_state *mas) in mas_pause() argument
5902 mas->status = ma_pause; in mas_pause()
5903 mas->node = NULL; in mas_pause()
5915 static __always_inline bool mas_find_setup(struct ma_state *mas, unsigned long max, void **entry) in mas_find_setup() argument
5917 switch (mas->status) { in mas_find_setup()
5919 if (mas->last < max) in mas_find_setup()
5925 if (unlikely(mas->last >= max)) in mas_find_setup()
5928 mas->index = ++mas->last; in mas_find_setup()
5929 mas->status = ma_start; in mas_find_setup()
5932 if (unlikely(mas->last >= max)) in mas_find_setup()
5935 mas->index = mas->last; in mas_find_setup()
5936 mas->status = ma_start; in mas_find_setup()
5940 if (unlikely(mas->index >= max)) { in mas_find_setup()
5941 mas->status = ma_overflow; in mas_find_setup()
5945 mas->status = ma_active; in mas_find_setup()
5946 *entry = mas_walk(mas); in mas_find_setup()
5951 if (unlikely(mas->last >= max)) in mas_find_setup()
5954 mas->status = ma_active; in mas_find_setup()
5955 *entry = mas_walk(mas); in mas_find_setup()
5965 if (mas_is_start(mas)) { in mas_find_setup()
5967 if (mas->index > max) in mas_find_setup()
5970 *entry = mas_walk(mas); in mas_find_setup()
5976 if (unlikely(mas_is_ptr(mas))) in mas_find_setup()
5979 if (unlikely(mas_is_none(mas))) in mas_find_setup()
5982 if (mas->index == max) in mas_find_setup()
5988 mas->status = ma_none; in mas_find_setup()
5989 mas->index = 1; in mas_find_setup()
5990 mas->last = ULONG_MAX; in mas_find_setup()
6006 void *mas_find(struct ma_state *mas, unsigned long max) in mas_find() argument
6010 if (mas_find_setup(mas, max, &entry)) in mas_find()
6014 entry = mas_next_slot(mas, max, false); in mas_find()
6016 mas->status = ma_active; in mas_find()
6033 void *mas_find_range(struct ma_state *mas, unsigned long max) in mas_find_range() argument
6037 if (mas_find_setup(mas, max, &entry)) in mas_find_range()
6041 return mas_next_slot(mas, max, true); in mas_find_range()
6053 static bool mas_find_rev_setup(struct ma_state *mas, unsigned long min, in mas_find_rev_setup() argument
6057 switch (mas->status) { in mas_find_rev_setup()
6063 if (unlikely(mas->index <= min)) { in mas_find_rev_setup()
6064 mas->status = ma_underflow; in mas_find_rev_setup()
6067 mas->last = --mas->index; in mas_find_rev_setup()
6068 mas->status = ma_start; in mas_find_rev_setup()
6071 if (mas->index <= min) in mas_find_rev_setup()
6074 mas->last = mas->index; in mas_find_rev_setup()
6075 mas->status = ma_start; in mas_find_rev_setup()
6078 if (unlikely(mas->index <= min)) { in mas_find_rev_setup()
6079 mas->status = ma_underflow; in mas_find_rev_setup()
6083 mas->status = ma_active; in mas_find_rev_setup()
6086 if (unlikely(mas->index <= min)) in mas_find_rev_setup()
6089 mas->status = ma_active; in mas_find_rev_setup()
6097 if (mas_is_start(mas)) { in mas_find_rev_setup()
6099 if (mas->index < min) in mas_find_rev_setup()
6102 *entry = mas_walk(mas); in mas_find_rev_setup()
6107 if (unlikely(mas_is_ptr(mas))) in mas_find_rev_setup()
6110 if (unlikely(mas_is_none(mas))) { in mas_find_rev_setup()
6115 mas->last = mas->index = 0; in mas_find_rev_setup()
6116 mas->status = ma_root; in mas_find_rev_setup()
6117 *entry = mas_root(mas); in mas_find_rev_setup()
6122 if (mas->index < min) in mas_find_rev_setup()
6128 mas->status = ma_none; in mas_find_rev_setup()
6145 void *mas_find_rev(struct ma_state *mas, unsigned long min) in mas_find_rev() argument
6149 if (mas_find_rev_setup(mas, min, &entry)) in mas_find_rev()
6153 return mas_prev_slot(mas, min, false); in mas_find_rev()
6171 void *mas_find_range_rev(struct ma_state *mas, unsigned long min) in mas_find_range_rev() argument
6175 if (mas_find_rev_setup(mas, min, &entry)) in mas_find_range_rev()
6179 return mas_prev_slot(mas, min, true); in mas_find_range_rev()
6194 void *mas_erase(struct ma_state *mas) in mas_erase() argument
6197 unsigned long index = mas->index; in mas_erase()
6198 MA_WR_STATE(wr_mas, mas, NULL); in mas_erase()
6200 if (!mas_is_active(mas) || !mas_is_start(mas)) in mas_erase()
6201 mas->status = ma_start; in mas_erase()
6204 entry = mas_state_walk(mas); in mas_erase()
6209 mas_reset(mas); in mas_erase()
6211 if (mas_nomem(mas, GFP_KERNEL)) { in mas_erase()
6213 mas->index = mas->last = index; in mas_erase()
6217 if (mas_is_err(mas)) in mas_erase()
6222 mas_destroy(mas); in mas_erase()
6234 bool mas_nomem(struct ma_state *mas, gfp_t gfp) in mas_nomem() argument
6235 __must_hold(mas->tree->ma_lock) in mas_nomem()
6237 if (likely(mas->node != MA_ERROR(-ENOMEM))) in mas_nomem()
6240 if (gfpflags_allow_blocking(gfp) && !mt_external_lock(mas->tree)) { in mas_nomem()
6241 mtree_unlock(mas->tree); in mas_nomem()
6242 mas_alloc_nodes(mas, gfp); in mas_nomem()
6243 mtree_lock(mas->tree); in mas_nomem()
6245 mas_alloc_nodes(mas, gfp); in mas_nomem()
6248 if (!mas_allocated(mas)) in mas_nomem()
6251 mas->status = ma_start; in mas_nomem()
6271 MA_STATE(mas, mt, index, index); in mtree_load()
6274 trace_ma_read(__func__, &mas); in mtree_load()
6277 entry = mas_start(&mas); in mtree_load()
6278 if (unlikely(mas_is_none(&mas))) in mtree_load()
6281 if (unlikely(mas_is_ptr(&mas))) { in mtree_load()
6288 entry = mtree_lookup_walk(&mas); in mtree_load()
6289 if (!entry && unlikely(mas_is_start(&mas))) in mtree_load()
6314 MA_STATE(mas, mt, index, last); in mtree_store_range()
6317 trace_ma_write(__func__, &mas, 0, entry); in mtree_store_range()
6325 ret = mas_store_gfp(&mas, entry, gfp); in mtree_store_range()
6410 MA_STATE(mas, mt, 0, 0); in mtree_alloc_range()
6419 ret = mas_empty_area(&mas, min, max, size); in mtree_alloc_range()
6423 mas_insert(&mas, entry); in mtree_alloc_range()
6428 if (mas_nomem(&mas, gfp)) in mtree_alloc_range()
6431 if (mas_is_err(&mas)) in mtree_alloc_range()
6432 ret = xa_err(mas.node); in mtree_alloc_range()
6434 *startp = mas.index; in mtree_alloc_range()
6438 mas_destroy(&mas); in mtree_alloc_range()
6472 MA_STATE(mas, mt, 0, 0); in mtree_alloc_cyclic()
6479 ret = mas_alloc_cyclic(&mas, startp, entry, range_lo, range_hi, in mtree_alloc_cyclic()
6492 MA_STATE(mas, mt, 0, 0); in mtree_alloc_rrange()
6501 ret = mas_empty_area_rev(&mas, min, max, size); in mtree_alloc_rrange()
6505 mas_insert(&mas, entry); in mtree_alloc_rrange()
6510 if (mas_nomem(&mas, gfp)) in mtree_alloc_rrange()
6513 if (mas_is_err(&mas)) in mtree_alloc_rrange()
6514 ret = xa_err(mas.node); in mtree_alloc_rrange()
6516 *startp = mas.index; in mtree_alloc_rrange()
6520 mas_destroy(&mas); in mtree_alloc_rrange()
6539 MA_STATE(mas, mt, index, index); in mtree_erase()
6540 trace_ma_op(__func__, &mas); in mtree_erase()
6543 entry = mas_erase(&mas); in mtree_erase()
6559 static void mas_dup_free(struct ma_state *mas) in mas_dup_free() argument
6567 if (mas_is_none(mas)) in mas_dup_free()
6570 while (!mte_is_root(mas->node)) { in mas_dup_free()
6571 mas_ascend(mas); in mas_dup_free()
6572 if (mas->offset) { in mas_dup_free()
6573 mas->offset--; in mas_dup_free()
6575 mas_descend(mas); in mas_dup_free()
6576 mas->offset = mas_data_end(mas); in mas_dup_free()
6577 } while (!mte_is_leaf(mas->node)); in mas_dup_free()
6579 mas_ascend(mas); in mas_dup_free()
6582 node = mte_to_node(mas->node); in mas_dup_free()
6583 type = mte_node_type(mas->node); in mas_dup_free()
6585 count = mas_data_end(mas) + 1; in mas_dup_free()
6591 node = mte_to_node(mas->node); in mas_dup_free()
6604 static inline void mas_copy_node(struct ma_state *mas, struct ma_state *new_mas, in mas_copy_node() argument
6607 struct maple_node *node = mte_to_node(mas->node); in mas_copy_node()
6627 static inline void mas_dup_alloc(struct ma_state *mas, struct ma_state *new_mas, in mas_dup_alloc() argument
6630 struct maple_node *node = mte_to_node(mas->node); in mas_dup_alloc()
6639 type = mte_node_type(mas->node); in mas_dup_alloc()
6641 request = mas_data_end(mas) + 1; in mas_dup_alloc()
6645 mas_set_err(mas, -ENOMEM); in mas_dup_alloc()
6652 val = (unsigned long)mt_slot_locked(mas->tree, slots, i); in mas_dup_alloc()
6671 static inline void mas_dup_build(struct ma_state *mas, struct ma_state *new_mas, in mas_dup_build() argument
6679 if (unlikely(mt_attr(mas->tree) != mt_attr(new_mas->tree)) || in mas_dup_build()
6681 mas_set_err(mas, -EINVAL); in mas_dup_build()
6685 root = mas_start(mas); in mas_dup_build()
6686 if (mas_is_ptr(mas) || mas_is_none(mas)) in mas_dup_build()
6692 mas_set_err(mas, -ENOMEM); in mas_dup_build()
6696 type = mte_node_type(mas->node); in mas_dup_build()
6703 mas_copy_node(mas, new_mas, parent); in mas_dup_build()
6704 if (!mte_is_leaf(mas->node)) { in mas_dup_build()
6706 mas_dup_alloc(mas, new_mas, gfp); in mas_dup_build()
6707 if (unlikely(mas_is_err(mas))) in mas_dup_build()
6714 if (mas->max == ULONG_MAX) in mas_dup_build()
6719 mas_ascend(mas); in mas_dup_build()
6721 } while (mas->offset == mas_data_end(mas)); in mas_dup_build()
6724 mas->offset++; in mas_dup_build()
6728 mas_descend(mas); in mas_dup_build()
6731 mas->offset = 0; in mas_dup_build()
6739 new_mas->tree->ma_flags = mas->tree->ma_flags; in mas_dup_build()
6767 MA_STATE(mas, mt, 0, 0); in __mt_dup()
6770 mas_dup_build(&mas, &new_mas, gfp); in __mt_dup()
6771 if (unlikely(mas_is_err(&mas))) { in __mt_dup()
6772 ret = xa_err(mas.node); in __mt_dup()
6804 MA_STATE(mas, mt, 0, 0); in mtree_dup()
6808 mas_lock_nested(&mas, SINGLE_DEPTH_NESTING); in mtree_dup()
6809 mas_dup_build(&mas, &new_mas, gfp); in mtree_dup()
6810 mas_unlock(&mas); in mtree_dup()
6811 if (unlikely(mas_is_err(&mas))) { in mtree_dup()
6812 ret = xa_err(mas.node); in mtree_dup()
6872 MA_STATE(mas, mt, *index, *index); in mt_find()
6878 trace_ma_read(__func__, &mas); in mt_find()
6885 entry = mas_state_walk(&mas); in mt_find()
6886 if (mas_is_start(&mas)) in mt_find()
6895 while (mas_is_active(&mas) && (mas.last < max)) { in mt_find()
6896 entry = mas_next_slot(&mas, max, false); in mt_find()
6906 *index = mas.last + 1; in mt_find()
7017 static inline struct maple_enode *mas_get_slot(struct ma_state *mas, in mas_get_slot() argument
7020 return mas_slot(mas, ma_slots(mas_mn(mas), mte_node_type(mas->node)), in mas_get_slot()
7025 static void mas_dfs_postorder(struct ma_state *mas, unsigned long max) in mas_dfs_postorder() argument
7028 struct maple_enode *p, *mn = mas->node; in mas_dfs_postorder()
7031 mas_next_node(mas, mas_mn(mas), max); in mas_dfs_postorder()
7032 if (!mas_is_overflow(mas)) in mas_dfs_postorder()
7038 mas->node = mn; in mas_dfs_postorder()
7039 mas_ascend(mas); in mas_dfs_postorder()
7041 p = mas->node; in mas_dfs_postorder()
7042 p_min = mas->min; in mas_dfs_postorder()
7043 p_max = mas->max; in mas_dfs_postorder()
7044 mas_prev_node(mas, 0); in mas_dfs_postorder()
7045 } while (!mas_is_underflow(mas)); in mas_dfs_postorder()
7047 mas->node = p; in mas_dfs_postorder()
7048 mas->max = p_max; in mas_dfs_postorder()
7049 mas->min = p_min; in mas_dfs_postorder()
7258 static void mas_validate_gaps(struct ma_state *mas) in mas_validate_gaps() argument
7260 struct maple_enode *mte = mas->node; in mas_validate_gaps()
7262 enum maple_type mt = mte_node_type(mas->node); in mas_validate_gaps()
7264 unsigned long p_end, p_start = mas->min; in mas_validate_gaps()
7272 if (mas_get_slot(mas, i)) { in mas_validate_gaps()
7285 p_end = mas_safe_pivot(mas, pivots, i, mt); in mas_validate_gaps()
7288 if (!mas_get_slot(mas, i)) in mas_validate_gaps()
7291 void *entry = mas_get_slot(mas, i); in mas_validate_gaps()
7294 MT_BUG_ON(mas->tree, !entry); in mas_validate_gaps()
7298 mas_mn(mas), i, gap, p_end, p_start, in mas_validate_gaps()
7300 MT_BUG_ON(mas->tree, gap > p_end - p_start + 1); in mas_validate_gaps()
7308 if (p_end >= mas->max) in mas_validate_gaps()
7314 MT_BUG_ON(mas->tree, !gaps); in mas_validate_gaps()
7318 MT_BUG_ON(mas->tree, 1); in mas_validate_gaps()
7324 MT_BUG_ON(mas->tree, 1); in mas_validate_gaps()
7331 MT_BUG_ON(mas->tree, 1); in mas_validate_gaps()
7339 p_slot = mte_parent_slot(mas->node); in mas_validate_gaps()
7341 MT_BUG_ON(mas->tree, max_gap > mas->max); in mas_validate_gaps()
7342 if (ma_gaps(p_mn, mas_parent_type(mas, mte))[p_slot] != max_gap) { in mas_validate_gaps()
7344 mt_dump(mas->tree, mt_dump_hex); in mas_validate_gaps()
7345 MT_BUG_ON(mas->tree, 1); in mas_validate_gaps()
7349 static void mas_validate_parent_slot(struct ma_state *mas) in mas_validate_parent_slot() argument
7358 if (mte_is_root(mas->node)) in mas_validate_parent_slot()
7361 p_slot = mte_parent_slot(mas->node); in mas_validate_parent_slot()
7362 p_type = mas_parent_type(mas, mas->node); in mas_validate_parent_slot()
7363 parent = mte_parent(mas->node); in mas_validate_parent_slot()
7365 MT_BUG_ON(mas->tree, mas_mn(mas) == parent); in mas_validate_parent_slot()
7370 node = mas_slot(mas, slots, i); in mas_validate_parent_slot()
7372 if (node != mas->node) in mas_validate_parent_slot()
7374 parent, i, mas_mn(mas)); in mas_validate_parent_slot()
7375 MT_BUG_ON(mas->tree, node != mas->node); in mas_validate_parent_slot()
7376 } else if (node == mas->node) { in mas_validate_parent_slot()
7378 mas_mn(mas), parent, i, p_slot); in mas_validate_parent_slot()
7379 MT_BUG_ON(mas->tree, node == mas->node); in mas_validate_parent_slot()
7384 static void mas_validate_child_slot(struct ma_state *mas) in mas_validate_child_slot() argument
7386 enum maple_type type = mte_node_type(mas->node); in mas_validate_child_slot()
7387 void __rcu **slots = ma_slots(mte_to_node(mas->node), type); in mas_validate_child_slot()
7388 unsigned long *pivots = ma_pivots(mte_to_node(mas->node), type); in mas_validate_child_slot()
7392 if (mte_is_leaf(mas->node)) in mas_validate_child_slot()
7396 child = mas_slot(mas, slots, i); in mas_validate_child_slot()
7400 mas_mn(mas), i); in mas_validate_child_slot()
7401 MT_BUG_ON(mas->tree, 1); in mas_validate_child_slot()
7406 mas_mn(mas), i, mte_to_node(child), in mas_validate_child_slot()
7408 MT_BUG_ON(mas->tree, 1); in mas_validate_child_slot()
7411 if (mte_parent(child) != mte_to_node(mas->node)) { in mas_validate_child_slot()
7414 mte_to_node(mas->node)); in mas_validate_child_slot()
7415 MT_BUG_ON(mas->tree, 1); in mas_validate_child_slot()
7418 if (i < mt_pivots[type] && pivots[i] == mas->max) in mas_validate_child_slot()
7428 static void mas_validate_limits(struct ma_state *mas) in mas_validate_limits() argument
7432 enum maple_type type = mte_node_type(mas->node); in mas_validate_limits()
7433 void __rcu **slots = ma_slots(mte_to_node(mas->node), type); in mas_validate_limits()
7434 unsigned long *pivots = ma_pivots(mas_mn(mas), type); in mas_validate_limits()
7439 piv = mas_safe_pivot(mas, pivots, i, type); in mas_validate_limits()
7443 mas_mn(mas), i); in mas_validate_limits()
7444 MAS_WARN_ON(mas, 1); in mas_validate_limits()
7449 mas_mn(mas), i, piv, prev_piv); in mas_validate_limits()
7450 MAS_WARN_ON(mas, piv < prev_piv); in mas_validate_limits()
7453 if (piv < mas->min) { in mas_validate_limits()
7454 pr_err(PTR_FMT "[%u] %lu < %lu\n", mas_mn(mas), i, in mas_validate_limits()
7455 piv, mas->min); in mas_validate_limits()
7456 MAS_WARN_ON(mas, piv < mas->min); in mas_validate_limits()
7458 if (piv > mas->max) { in mas_validate_limits()
7459 pr_err(PTR_FMT "[%u] %lu > %lu\n", mas_mn(mas), i, in mas_validate_limits()
7460 piv, mas->max); in mas_validate_limits()
7461 MAS_WARN_ON(mas, piv > mas->max); in mas_validate_limits()
7464 if (piv == mas->max) in mas_validate_limits()
7468 if (mas_data_end(mas) != i) { in mas_validate_limits()
7470 mas_mn(mas), mas_data_end(mas), i); in mas_validate_limits()
7471 MT_BUG_ON(mas->tree, 1); in mas_validate_limits()
7475 void *entry = mas_slot(mas, slots, i); in mas_validate_limits()
7479 mas_mn(mas), i, entry); in mas_validate_limits()
7480 MT_BUG_ON(mas->tree, entry != NULL); in mas_validate_limits()
7490 mas_mn(mas), i, piv); in mas_validate_limits()
7491 MAS_WARN_ON(mas, i < mt_pivots[type] - 1); in mas_validate_limits()
7501 MA_STATE(mas, mt, 0, 0); in mt_validate_nulls()
7503 mas_start(&mas); in mt_validate_nulls()
7504 if (mas_is_none(&mas) || (mas_is_ptr(&mas))) in mt_validate_nulls()
7507 while (!mte_is_leaf(mas.node)) in mt_validate_nulls()
7508 mas_descend(&mas); in mt_validate_nulls()
7510 slots = ma_slots(mte_to_node(mas.node), mte_node_type(mas.node)); in mt_validate_nulls()
7512 entry = mas_slot(&mas, slots, offset); in mt_validate_nulls()
7515 mas_mn(&mas), offset); in mt_validate_nulls()
7519 if (offset == mas_data_end(&mas)) { in mt_validate_nulls()
7520 mas_next_node(&mas, mas_mn(&mas), ULONG_MAX); in mt_validate_nulls()
7521 if (mas_is_overflow(&mas)) in mt_validate_nulls()
7524 slots = ma_slots(mte_to_node(mas.node), in mt_validate_nulls()
7525 mte_node_type(mas.node)); in mt_validate_nulls()
7530 } while (!mas_is_overflow(&mas)); in mt_validate_nulls()
7539 __must_hold(mas->tree->ma_lock) in mt_validate()
7543 MA_STATE(mas, mt, 0, 0); in mt_validate()
7544 mas_start(&mas); in mt_validate()
7545 if (!mas_is_active(&mas)) in mt_validate()
7548 while (!mte_is_leaf(mas.node)) in mt_validate()
7549 mas_descend(&mas); in mt_validate()
7551 while (!mas_is_overflow(&mas)) { in mt_validate()
7552 MAS_WARN_ON(&mas, mte_dead_node(mas.node)); in mt_validate()
7553 end = mas_data_end(&mas); in mt_validate()
7554 if (MAS_WARN_ON(&mas, (end < mt_min_slot_count(mas.node)) && in mt_validate()
7555 (!mte_is_root(mas.node)))) { in mt_validate()
7557 end, mas_mn(&mas)); in mt_validate()
7560 mas_validate_parent_slot(&mas); in mt_validate()
7561 mas_validate_limits(&mas); in mt_validate()
7562 mas_validate_child_slot(&mas); in mt_validate()
7564 mas_validate_gaps(&mas); in mt_validate()
7565 mas_dfs_postorder(&mas, ULONG_MAX); in mt_validate()
7571 void mas_dump(const struct ma_state *mas) in mas_dump() argument
7574 mas->tree, mas->node); in mas_dump()
7575 switch (mas->status) { in mas_dump()
7603 switch (mas->store_type) { in mas_dump()
7636 pr_err("[%u/%u] index=%lx last=%lx\n", mas->offset, mas->end, in mas_dump()
7637 mas->index, mas->last); in mas_dump()
7639 mas->min, mas->max, mas->alloc, mas->depth, mas->mas_flags); in mas_dump()
7640 if (mas->index > mas->last) in mas_dump()
7650 wr_mas->type, wr_mas->offset_end, wr_mas->mas->end, in mas_wr_dump()