2064 static noinline_for_kasan void mas_store_b_node(struct ma_wr_state *wr_mas,  in mas_store_b_node()  argument
2071 	struct ma_state *mas = wr_mas->mas;  in mas_store_b_node()
2073 	b_node->type = wr_mas->type;  in mas_store_b_node()
2086 		b_node->slot[b_end] = wr_mas->content;  in mas_store_b_node()
2087 		if (!wr_mas->content)  in mas_store_b_node()
2094 	b_node->slot[b_end] = wr_mas->entry;  in mas_store_b_node()
2102 	piv = mas_safe_pivot(mas, wr_mas->pivots, offset_end, wr_mas->type);  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()
2111 		b_node->slot[++b_end] = wr_mas->content;  in mas_store_b_node()
2112 		if (!wr_mas->content)  in mas_store_b_node()
2201 static inline void mas_wr_node_walk(struct ma_wr_state *wr_mas)  in mas_wr_node_walk()  argument
2203 	struct ma_state *mas = wr_mas->mas;  in mas_wr_node_walk()
2206 	if (unlikely(ma_is_dense(wr_mas->type))) {  in mas_wr_node_walk()
2207 		wr_mas->r_max = wr_mas->r_min = mas->index;  in mas_wr_node_walk()
2212 	wr_mas->node = mas_mn(wr_mas->mas);  in mas_wr_node_walk()
2213 	wr_mas->pivots = ma_pivots(wr_mas->node, wr_mas->type);  in mas_wr_node_walk()
2214 	count = mas->end = ma_data_end(wr_mas->node, wr_mas->type,  in mas_wr_node_walk()
2215 				       wr_mas->pivots, mas->max);  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()
2312 	MA_WR_STATE(wr_mas, mast->orig_r,  NULL);  in mast_ascend()
2322 	wr_mas.type = mte_node_type(mast->orig_r->node);  in mast_ascend()
2323 	mas_wr_node_walk(&wr_mas);  in mast_ascend()
2327 	wr_mas.mas = mast->orig_l;  in mast_ascend()
2328 	wr_mas.type = mte_node_type(mast->orig_l->node);  in mast_ascend()
2329 	mas_wr_node_walk(&wr_mas);  in mast_ascend()
2331 	mast->bn->type = wr_mas.type;  in mast_ascend()
3378 static noinline_for_kasan void mas_commit_b_node(struct ma_wr_state *wr_mas,  in mas_commit_b_node()  argument
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()
3468 static bool mas_is_span_wr(struct ma_wr_state *wr_mas)  in mas_is_span_wr()  argument
3470 	unsigned long max = wr_mas->r_max;  in mas_is_span_wr()
3471 	unsigned long last = wr_mas->mas->last;  in mas_is_span_wr()
3472 	enum maple_type type = wr_mas->type;  in mas_is_span_wr()
3473 	void *entry = wr_mas->entry;  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()
3498 static inline void mas_wr_walk_descend(struct ma_wr_state *wr_mas)  in mas_wr_walk_descend()  argument
3500 	wr_mas->type = mte_node_type(wr_mas->mas->node);  in mas_wr_walk_descend()
3501 	mas_wr_node_walk(wr_mas);  in mas_wr_walk_descend()
3502 	wr_mas->slots = ma_slots(wr_mas->node, wr_mas->type);  in mas_wr_walk_descend()
3505 static inline void mas_wr_walk_traverse(struct ma_wr_state *wr_mas)  in mas_wr_walk_traverse()  argument
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()
3521 static bool mas_wr_walk(struct ma_wr_state *wr_mas)  in mas_wr_walk()  argument
3523 	struct ma_state *mas = wr_mas->mas;  in mas_wr_walk()
3526 		mas_wr_walk_descend(wr_mas);  in mas_wr_walk()
3527 		if (unlikely(mas_is_span_wr(wr_mas)))  in mas_wr_walk()
3530 		wr_mas->content = mas_slot_locked(mas, wr_mas->slots,  in mas_wr_walk()
3532 		if (ma_is_leaf(wr_mas->type))  in mas_wr_walk()
3535 		mas_wr_walk_traverse(wr_mas);  in mas_wr_walk()
3541 static void mas_wr_walk_index(struct ma_wr_state *wr_mas)  in mas_wr_walk_index()  argument
3543 	struct ma_state *mas = wr_mas->mas;  in mas_wr_walk_index()
3546 		mas_wr_walk_descend(wr_mas);  in mas_wr_walk_index()
3547 		wr_mas->content = mas_slot_locked(mas, wr_mas->slots,  in mas_wr_walk_index()
3549 		if (ma_is_leaf(wr_mas->type))  in mas_wr_walk_index()
3551 		mas_wr_walk_traverse(wr_mas);  in mas_wr_walk_index()
3704 static noinline void mas_wr_spanning_store(struct ma_wr_state *wr_mas)  in mas_wr_spanning_store()  argument
3714 	MA_WR_STATE(r_wr_mas, &r_mas, wr_mas->entry);  in mas_wr_spanning_store()
3715 	MA_WR_STATE(l_wr_mas, &l_mas, wr_mas->entry);  in mas_wr_spanning_store()
3729 	mas = wr_mas->mas;  in mas_wr_spanning_store()
3733 		return mas_new_root(mas, wr_mas->entry);  in mas_wr_spanning_store()
3758 	if (!wr_mas->entry) {  in mas_wr_spanning_store()
3768 		return mas_new_root(mas, wr_mas->entry);  in mas_wr_spanning_store()
3797 static inline void mas_wr_node_store(struct ma_wr_state *wr_mas,  in mas_wr_node_store()  argument
3800 	struct ma_state *mas = wr_mas->mas;  in mas_wr_node_store()
3803 	unsigned char dst_offset, offset_end = wr_mas->offset_end;  in mas_wr_node_store()
3805 	unsigned char copy_size, node_pivots = mt_pivots[wr_mas->type];  in mas_wr_node_store()
3808 	if (mas->last == wr_mas->end_piv)  in mas_wr_node_store()
3810 	else if (unlikely(wr_mas->r_max == ULONG_MAX))  in mas_wr_node_store()
3811 		mas_bulk_rebalance(mas, mas->end, wr_mas->type);  in mas_wr_node_store()
3822 	dst_pivots = ma_pivots(newnode, wr_mas->type);  in mas_wr_node_store()
3823 	dst_slots = ma_slots(newnode, wr_mas->type);  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()
3837 	rcu_assign_pointer(dst_slots[mas->offset], wr_mas->entry);  in mas_wr_node_store()
3849 	memcpy(dst_slots + dst_offset, wr_mas->slots + offset_end,  in mas_wr_node_store()
3851 	memcpy(dst_pivots + dst_offset, wr_mas->pivots + offset_end,  in mas_wr_node_store()
3862 		mas->node = mt_mk_node(newnode, wr_mas->type);  in mas_wr_node_store()
3865 		memcpy(wr_mas->node, newnode, sizeof(struct maple_node));  in mas_wr_node_store()
3867 	trace_ma_write(__func__, mas, 0, wr_mas->entry);  in mas_wr_node_store()
3877 static inline void mas_wr_slot_store(struct ma_wr_state *wr_mas)  in mas_wr_slot_store()  argument
3879 	struct ma_state *mas = wr_mas->mas;  in mas_wr_slot_store()
3881 	void __rcu **slots = wr_mas->slots;  in mas_wr_slot_store()
3887 	if (wr_mas->offset_end - offset == 1) {  in mas_wr_slot_store()
3888 		if (mas->index == wr_mas->r_min) {  in mas_wr_slot_store()
3890 			rcu_assign_pointer(slots[offset], wr_mas->entry);  in mas_wr_slot_store()
3891 			wr_mas->pivots[offset] = mas->last;  in mas_wr_slot_store()
3894 			rcu_assign_pointer(slots[offset + 1], wr_mas->entry);  in mas_wr_slot_store()
3895 			wr_mas->pivots[offset] = mas->index - 1;  in mas_wr_slot_store()
3905 		rcu_assign_pointer(slots[offset + 1], wr_mas->entry);  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()
3911 	trace_ma_write(__func__, mas, 0, wr_mas->entry);  in mas_wr_slot_store()
3916 	if (!wr_mas->entry || gap)  in mas_wr_slot_store()
3922 static inline void mas_wr_extend_null(struct ma_wr_state *wr_mas)  in mas_wr_extend_null()  argument
3924 	struct ma_state *mas = wr_mas->mas;  in mas_wr_extend_null()
3926 	if (!wr_mas->slots[wr_mas->offset_end]) {  in mas_wr_extend_null()
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()
3933 		    !wr_mas->slots[wr_mas->offset_end + 1]) {  in mas_wr_extend_null()
3934 			wr_mas->offset_end++;  in mas_wr_extend_null()
3935 			if (wr_mas->offset_end == mas->end)  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()
3943 	if (!wr_mas->content) {  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()
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()
3958 static inline void mas_wr_end_piv(struct ma_wr_state *wr_mas)  in mas_wr_end_piv()  argument
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()
3962 		wr_mas->offset_end++;  in mas_wr_end_piv()
3964 	if (wr_mas->offset_end < wr_mas->mas->end)  in mas_wr_end_piv()
3965 		wr_mas->end_piv = wr_mas->pivots[wr_mas->offset_end];  in mas_wr_end_piv()
3967 		wr_mas->end_piv = wr_mas->mas->max;  in mas_wr_end_piv()
3970 static inline unsigned char mas_wr_new_end(struct ma_wr_state *wr_mas)  in mas_wr_new_end()  argument
3972 	struct ma_state *mas = wr_mas->mas;  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()
3994 static inline void mas_wr_append(struct ma_wr_state *wr_mas,  in mas_wr_append()  argument
3997 	struct ma_state *mas = wr_mas->mas;  in mas_wr_append()
4001 	if (new_end < mt_pivots[wr_mas->type]) {  in mas_wr_append()
4002 		wr_mas->pivots[new_end] = wr_mas->pivots[end];  in mas_wr_append()
4003 		ma_set_meta(wr_mas->node, wr_mas->type, 0, new_end);  in mas_wr_append()
4006 	slots = wr_mas->slots;  in mas_wr_append()
4008 		if (mas->last == wr_mas->r_max) {  in mas_wr_append()
4010 			rcu_assign_pointer(slots[new_end], wr_mas->entry);  in mas_wr_append()
4011 			wr_mas->pivots[end] = mas->index - 1;  in mas_wr_append()
4015 			rcu_assign_pointer(slots[new_end], wr_mas->content);  in mas_wr_append()
4016 			wr_mas->pivots[end] = mas->last;  in mas_wr_append()
4017 			rcu_assign_pointer(slots[end], wr_mas->entry);  in mas_wr_append()
4021 		rcu_assign_pointer(slots[new_end], wr_mas->content);  in mas_wr_append()
4022 		wr_mas->pivots[end + 1] = mas->last;  in mas_wr_append()
4023 		rcu_assign_pointer(slots[end + 1], wr_mas->entry);  in mas_wr_append()
4024 		wr_mas->pivots[end] = mas->index - 1;  in mas_wr_append()
4028 	if (!wr_mas->content || !wr_mas->entry)  in mas_wr_append()
4032 	trace_ma_write(__func__, mas, new_end, wr_mas->entry);  in mas_wr_append()
4042 static void mas_wr_bnode(struct ma_wr_state *wr_mas)  in mas_wr_bnode()  argument
4046 	trace_ma_write(__func__, wr_mas->mas, 0, wr_mas->entry);  in mas_wr_bnode()
4048 	mas_store_b_node(wr_mas, &b_node, wr_mas->offset_end);  in mas_wr_bnode()
4049 	mas_commit_b_node(wr_mas, &b_node);  in mas_wr_bnode()
4056 static inline void mas_wr_store_entry(struct ma_wr_state *wr_mas)  in mas_wr_store_entry()  argument
4058 	struct ma_state *mas = wr_mas->mas;  in mas_wr_store_entry()
4059 	unsigned char new_end = mas_wr_new_end(wr_mas);  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()
4073 		if (!!wr_mas->entry ^ !!wr_mas->content)  in mas_wr_store_entry()
4077 		mas_wr_append(wr_mas, new_end);  in mas_wr_store_entry()
4080 		mas_wr_slot_store(wr_mas);  in mas_wr_store_entry()
4083 		mas_wr_node_store(wr_mas, new_end);  in mas_wr_store_entry()
4086 		mas_wr_spanning_store(wr_mas);  in mas_wr_store_entry()
4090 		mas_wr_bnode(wr_mas);  in mas_wr_store_entry()
4097 static inline void mas_wr_prealloc_setup(struct ma_wr_state *wr_mas)  in mas_wr_prealloc_setup()  argument
4099 	struct ma_state *mas = wr_mas->mas;  in mas_wr_prealloc_setup()
4126 	if (wr_mas->entry)  in mas_wr_prealloc_setup()
4137 	wr_mas->content = mas_start(mas);  in mas_wr_prealloc_setup()
4195 static inline enum store_type mas_wr_store_type(struct ma_wr_state *wr_mas)  in mas_wr_store_type()  argument
4197 	struct ma_state *mas = wr_mas->mas;  in mas_wr_store_type()
4203 	if (unlikely(!mas_wr_walk(wr_mas)))  in mas_wr_store_type()
4207 	mas_wr_end_piv(wr_mas);  in mas_wr_store_type()
4208 	if (!wr_mas->entry)  in mas_wr_store_type()
4209 		mas_wr_extend_null(wr_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()
4217 	new_end = mas_wr_new_end(wr_mas);  in mas_wr_store_type()
4219 	if (new_end < mt_min_slots[wr_mas->type]) {  in mas_wr_store_type()
4225 	if (new_end >= mt_slots[wr_mas->type])  in mas_wr_store_type()
4232 		(wr_mas->offset_end - mas->offset == 1)))  in mas_wr_store_type()
4244 static inline void mas_wr_preallocate(struct ma_wr_state *wr_mas, void *entry)  in mas_wr_preallocate()  argument
4246 	struct ma_state *mas = wr_mas->mas;  in mas_wr_preallocate()
4249 	mas_wr_prealloc_setup(wr_mas);  in mas_wr_preallocate()
4250 	mas->store_type = mas_wr_store_type(wr_mas);  in mas_wr_preallocate()
4268 	MA_WR_STATE(wr_mas, mas, entry);  in mas_insert()
4284 	wr_mas.content = mas_start(mas);  in mas_insert()
4285 	if (wr_mas.content)  in mas_insert()
4288 	mas_wr_preallocate(&wr_mas, entry);  in mas_insert()
4298 		wr_mas.offset_end = mas->offset;  in mas_insert()
4299 		wr_mas.end_piv = wr_mas.r_max;  in mas_insert()
4301 		if (wr_mas.content || (mas->last > wr_mas.r_max))  in mas_insert()
4305 	mas_wr_store_entry(&wr_mas);  in mas_insert()
4306 	return wr_mas.content;  in mas_insert()
4310 	return wr_mas.content;  in mas_insert()
5371 	MA_WR_STATE(wr_mas, mas, entry);  in mas_store()
5392 	mas_wr_prealloc_setup(&wr_mas);  in mas_store()
5393 	mas->store_type = mas_wr_store_type(&wr_mas);  in mas_store()
5395 		mas_wr_store_entry(&wr_mas);  in mas_store()
5396 		MAS_WR_BUG_ON(&wr_mas, mas_is_err(mas));  in mas_store()
5397 		return wr_mas.content;  in mas_store()
5409 	mas_wr_store_entry(&wr_mas);  in mas_store()
5411 	return wr_mas.content;  in mas_store()
5428 	MA_WR_STATE(wr_mas, mas, entry);  in mas_store_gfp()
5432 	mas_wr_preallocate(&wr_mas, entry);  in mas_store_gfp()
5444 	mas_wr_store_entry(&wr_mas);  in mas_store_gfp()
5459 	MA_WR_STATE(wr_mas, mas, entry);  in mas_store_prealloc()
5462 		mas_wr_prealloc_setup(&wr_mas);  in mas_store_prealloc()
5466 	mas_wr_walk_descend(&wr_mas);  in mas_store_prealloc()
5469 		wr_mas.content = mas_slot_locked(mas, wr_mas.slots, mas->offset);  in mas_store_prealloc()
5470 		mas_wr_end_piv(&wr_mas);  in mas_store_prealloc()
5475 	mas_wr_store_entry(&wr_mas);  in mas_store_prealloc()
5476 	MAS_WR_BUG_ON(&wr_mas, mas_is_err(mas));  in mas_store_prealloc()
5491 	MA_WR_STATE(wr_mas, mas, entry);  in mas_preallocate()
5495 	mas_wr_prealloc_setup(&wr_mas);  in mas_preallocate()
5496 	mas->store_type = mas_wr_store_type(&wr_mas);  in mas_preallocate()
6198 	MA_WR_STATE(wr_mas, mas, NULL);  in mas_erase()
6210 	mas_wr_preallocate(&wr_mas, NULL);  in mas_erase()
6220 	mas_wr_store_entry(&wr_mas);  in mas_erase()
7645 void mas_wr_dump(const struct ma_wr_state *wr_mas)  in mas_wr_dump()  argument
7648 	       wr_mas->node, wr_mas->r_min, wr_mas->r_max);  in mas_wr_dump()
7650 	       wr_mas->type, wr_mas->offset_end, wr_mas->mas->end,  in mas_wr_dump()
7651 	       wr_mas->end_piv);  in mas_wr_dump()