[PATCH v3 0/4] Optimize the fast path of mas_store()

[PATCH v3 0/4] Optimize the fast path of mas_store()

[Peng Zhang]

Add fast paths for mas_wr_append() and mas_wr_slot_store() respectively.
The newly added fast path of mas_wr_append() is used in fork() and how
much it benefits fork() depends on how many VMAs are duplicated.

Changes since v2:
 - Add test for expanding range in RCU mode. [2/4]

v1: https://lore.kernel.org/lkml/20230602075353.5917-1-zhangpeng.00@bytedance.com/
v2: https://lore.kernel.org/lkml/20230609120347.63936-1-zhangpeng.00@bytedance.com/

Peng Zhang (4):
  maple_tree: add test for mas_wr_modify() fast path
  maple_tree: add test for expanding range in RCU mode
  maple_tree: optimize mas_wr_append(), also improve duplicating VMAs
  maple_tree: add a fast path case in mas_wr_slot_store()

 lib/maple_tree.c                 | 69 +++++++++++++++++++----------
 lib/test_maple_tree.c            | 65 +++++++++++++++++++++++++++
 tools/testing/radix-tree/maple.c | 75 ++++++++++++++++++++++++++++++++
 3 files changed, 186 insertions(+), 23 deletions(-)

-- 
2.20.1

[PATCH v3 1/4] maple_tree: add test for mas_wr_modify() fast path

[Peng Zhang]

Add tests for all cases of mas_wr_append() and mas_wr_slot_store().

Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com>
---
 lib/test_maple_tree.c | 65 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 65 insertions(+)

diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c
index 15d7b7bce7d6..9403472af3d7 100644
--- a/lib/test_maple_tree.c
+++ b/lib/test_maple_tree.c
@@ -1159,6 +1159,71 @@ static noinline void __init check_ranges(struct maple_tree *mt)
 	MT_BUG_ON(mt, !mt_height(mt));
 	mtree_destroy(mt);
 
+	/* Check in-place modifications */
+	mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
+	/* Append to the start of last range */
+	mt_set_non_kernel(50);
+	for (i = 0; i <= 500; i++) {
+		val = i * 5 + 1;
+		val2 = val + 4;
+		check_store_range(mt, val, val2, xa_mk_value(val), 0);
+	}
+
+	/* Append to the last range without touching any boundaries */
+	for (i = 0; i < 10; i++) {
+		val = val2 + 5;
+		val2 = val + 4;
+		check_store_range(mt, val, val2, xa_mk_value(val), 0);
+	}
+
+	/* Append to the end of last range */
+	val = val2;
+	for (i = 0; i < 10; i++) {
+		val += 5;
+		MT_BUG_ON(mt, mtree_test_store_range(mt, val, ULONG_MAX,
+						     xa_mk_value(val)) != 0);
+	}
+
+	/* Overwriting the range and over a part of the next range */
+	for (i = 10; i < 30; i += 2) {
+		val = i * 5 + 1;
+		val2 = val + 5;
+		check_store_range(mt, val, val2, xa_mk_value(val), 0);
+	}
+
+	/* Overwriting a part of the range and over the next range */
+	for (i = 50; i < 70; i += 2) {
+		val2 = i * 5;
+		val = val2 - 5;
+		check_store_range(mt, val, val2, xa_mk_value(val), 0);
+	}
+
+	/*
+	 * Expand the range, only partially overwriting the previous and
+	 * next ranges
+	 */
+	for (i = 100; i < 130; i += 3) {
+		val = i * 5 - 5;
+		val2 = i * 5 + 1;
+		check_store_range(mt, val, val2, xa_mk_value(val), 0);
+	}
+
+	/*
+	 * Expand the range, only partially overwriting the previous and
+	 * next ranges, in RCU mode
+	 */
+	mt_set_in_rcu(mt);
+	for (i = 150; i < 180; i += 3) {
+		val = i * 5 - 5;
+		val2 = i * 5 + 1;
+		check_store_range(mt, val, val2, xa_mk_value(val), 0);
+	}
+
+	MT_BUG_ON(mt, !mt_height(mt));
+	mt_validate(mt);
+	mt_set_non_kernel(0);
+	mtree_destroy(mt);
+
 	/* Test rebalance gaps */
 	mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
 	mt_set_non_kernel(50);
-- 
2.20.1

[PATCH v3 2/4] maple_tree: add test for expanding range in RCU mode

[Peng Zhang]

Add test for expanding range in RCU mode. If we use the fast path of the
slot store to expand range in RCU mode, this test will fail.

Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com>
---
 tools/testing/radix-tree/maple.c | 75 ++++++++++++++++++++++++++++++++
 1 file changed, 75 insertions(+)

diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c
index c42033172276..0887826946f9 100644
--- a/tools/testing/radix-tree/maple.c
+++ b/tools/testing/radix-tree/maple.c
@@ -45,6 +45,13 @@ struct rcu_test_struct2 {
 	unsigned long last[RCU_RANGE_COUNT];
 };
 
+struct rcu_test_struct3 {
+	struct maple_tree *mt;
+	unsigned long index;
+	unsigned long last;
+	bool stop;
+};
+
 struct rcu_reader_struct {
 	unsigned int id;
 	int mod;
@@ -34954,6 +34961,70 @@ void run_check_rcu(struct maple_tree *mt, struct rcu_test_struct *vals)
 	MT_BUG_ON(mt, !vals->seen_entry2);
 }
 
+static void *rcu_slot_store_reader(void *ptr)
+{
+	struct rcu_test_struct3 *test = ptr;
+	MA_STATE(mas, test->mt, test->index, test->index);
+
+	rcu_register_thread();
+
+	rcu_read_lock();
+	while (!test->stop) {
+		mas_walk(&mas);
+		/* The length of growth to both sides must be equal. */
+		RCU_MT_BUG_ON(test, (test->index - mas.index) !=
+				    (mas.last - test->last));
+	}
+	rcu_read_unlock();
+
+	rcu_unregister_thread();
+	return NULL;
+}
+
+static noinline void run_check_rcu_slot_store(struct maple_tree *mt)
+{
+	pthread_t readers[20];
+	int range_cnt = 200, i, limit = 10000;
+	unsigned long len = ULONG_MAX / range_cnt, start, end;
+	struct rcu_test_struct3 test = {.stop = false, .mt = mt};
+
+	start = range_cnt / 2 * len;
+	end = start + len - 1;
+	test.index = start;
+	test.last = end;
+
+	for (i = 0; i < range_cnt; i++) {
+		mtree_store_range(mt, i * len, i * len + len - 1,
+				  xa_mk_value(i * 100), GFP_KERNEL);
+	}
+
+	mt_set_in_rcu(mt);
+	MT_BUG_ON(mt, !mt_in_rcu(mt));
+
+	for (i = 0; i < ARRAY_SIZE(readers); i++) {
+		if (pthread_create(&readers[i], NULL, rcu_slot_store_reader,
+				   &test)) {
+			perror("creating reader thread");
+			exit(1);
+		}
+	}
+
+	usleep(5);
+
+	while (limit--) {
+		/* Step by step, expand the most middle range to both sides. */
+		mtree_store_range(mt, --start, ++end, xa_mk_value(100),
+				  GFP_KERNEL);
+	}
+
+	test.stop = true;
+
+	while (i--)
+		pthread_join(readers[i], NULL);
+
+	mt_validate(mt);
+}
+
 static noinline
 void run_check_rcu_slowread(struct maple_tree *mt, struct rcu_test_struct *vals)
 {
@@ -35206,6 +35277,10 @@ static noinline void __init check_rcu_threaded(struct maple_tree *mt)
 	run_check_rcu(mt, &vals);
 	mtree_destroy(mt);
 
+	/* Check expanding range in RCU mode */
+	mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
+	run_check_rcu_slot_store(mt);
+	mtree_destroy(mt);
 
 	/* Forward writer for rcu stress */
 	mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
-- 
2.20.1

[PATCH v3 3/4] maple_tree: optimize mas_wr_append(), also improve duplicating VMAs

[Peng Zhang]

When the new range can be completely covered by the original last range
without touching the boundaries on both sides, two new entries can be
appended to the end as a fast path. We update the original last pivot at
the end, and the newly appended two entries will not be accessed before
this, so it is also safe in RCU mode.

This is useful for sequential insertion, which is what we do in
dup_mmap(). Enabling BENCH_FORK in test_maple_tree and just running
bench_forking() gives the following time-consuming numbers:

before:               after:
17,874.83 msec        15,738.38 msec

It shows about a 12% performance improvement for duplicating VMAs.

Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com>
Reviewed-by: Liam R. Howlett <Liam.Howlett@oracle.com>
---
 lib/maple_tree.c | 33 ++++++++++++++++++++++-----------
 1 file changed, 22 insertions(+), 11 deletions(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index d2799c69a669..da4af6743b30 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -4202,10 +4202,10 @@ static inline unsigned char mas_wr_new_end(struct ma_wr_state *wr_mas)
  *
  * Return: True if appended, false otherwise
  */
-static inline bool mas_wr_append(struct ma_wr_state *wr_mas)
+static inline bool mas_wr_append(struct ma_wr_state *wr_mas,
+				 unsigned char new_end)
 {
 	unsigned char end = wr_mas->node_end;
-	unsigned char new_end = end + 1;
 	struct ma_state *mas = wr_mas->mas;
 	unsigned char node_pivots = mt_pivots[wr_mas->type];
 
@@ -4217,16 +4217,27 @@ static inline bool mas_wr_append(struct ma_wr_state *wr_mas)
 		ma_set_meta(wr_mas->node, maple_leaf_64, 0, new_end);
 	}
 
-	if (mas->last == wr_mas->r_max) {
-		/* Append to end of range */
-		rcu_assign_pointer(wr_mas->slots[new_end], wr_mas->entry);
-		wr_mas->pivots[end] = mas->index - 1;
-		mas->offset = new_end;
+	if (new_end == wr_mas->node_end + 1) {
+		if (mas->last == wr_mas->r_max) {
+			/* Append to end of range */
+			rcu_assign_pointer(wr_mas->slots[new_end],
+					   wr_mas->entry);
+			wr_mas->pivots[end] = mas->index - 1;
+			mas->offset = new_end;
+		} else {
+			/* Append to start of range */
+			rcu_assign_pointer(wr_mas->slots[new_end],
+					   wr_mas->content);
+			wr_mas->pivots[end] = mas->last;
+			rcu_assign_pointer(wr_mas->slots[end], wr_mas->entry);
+		}
 	} else {
-		/* Append to start of range */
+		/* Append to the range without touching any boundaries. */
 		rcu_assign_pointer(wr_mas->slots[new_end], wr_mas->content);
-		wr_mas->pivots[end] = mas->last;
-		rcu_assign_pointer(wr_mas->slots[end], wr_mas->entry);
+		wr_mas->pivots[end + 1] = mas->last;
+		rcu_assign_pointer(wr_mas->slots[end + 1], wr_mas->entry);
+		wr_mas->pivots[end] = mas->index - 1;
+		mas->offset = end + 1;
 	}
 
 	if (!wr_mas->content || !wr_mas->entry)
@@ -4273,7 +4284,7 @@ static inline void mas_wr_modify(struct ma_wr_state *wr_mas)
 		goto slow_path;
 
 	/* Attempt to append */
-	if (new_end == wr_mas->node_end + 1 && mas_wr_append(wr_mas))
+	if (mas_wr_append(wr_mas, new_end))
 		return;
 
 	if (new_end == wr_mas->node_end && mas_wr_slot_store(wr_mas))
-- 
2.20.1

[PATCH v3 4/4] maple_tree: add a fast path case in mas_wr_slot_store()

[Peng Zhang]

When expanding a range in two directions, only partially overwriting the
previous and next ranges, the number of entries will not be increased, so
we can just update the pivots as a fast path. However, it may introduce
potential risks in RCU mode (although it may pass the test), because it
updates two pivots. We only enable it in non-RCU mode for now.

Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com>
---
 lib/maple_tree.c | 36 ++++++++++++++++++++++++------------
 1 file changed, 24 insertions(+), 12 deletions(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index da4af6743b30..bff6531fd0bc 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -4100,23 +4100,35 @@ static inline bool mas_wr_slot_store(struct ma_wr_state *wr_mas)
 {
 	struct ma_state *mas = wr_mas->mas;
 	unsigned char offset = mas->offset;
+	void __rcu **slots = wr_mas->slots;
 	bool gap = false;
 
-	if (wr_mas->offset_end - offset != 1)
-		return false;
-
-	gap |= !mt_slot_locked(mas->tree, wr_mas->slots, offset);
-	gap |= !mt_slot_locked(mas->tree, wr_mas->slots, offset + 1);
+	gap |= !mt_slot_locked(mas->tree, slots, offset);
+	gap |= !mt_slot_locked(mas->tree, slots, offset + 1);
 
-	if (mas->index == wr_mas->r_min) {
-		/* Overwriting the range and over a part of the next range. */
-		rcu_assign_pointer(wr_mas->slots[offset], wr_mas->entry);
-		wr_mas->pivots[offset] = mas->last;
-	} else {
-		/* Overwriting a part of the range and over the next range */
-		rcu_assign_pointer(wr_mas->slots[offset + 1], wr_mas->entry);
+	if (wr_mas->offset_end - offset == 1) {
+		if (mas->index == wr_mas->r_min) {
+			/* Overwriting the range and a part of the next one */
+			rcu_assign_pointer(slots[offset], wr_mas->entry);
+			wr_mas->pivots[offset] = mas->last;
+		} else {
+			/* Overwriting a part of the range and the next one */
+			rcu_assign_pointer(slots[offset + 1], wr_mas->entry);
+			wr_mas->pivots[offset] = mas->index - 1;
+			mas->offset++; /* Keep mas accurate. */
+		}
+	} else if (!mt_in_rcu(mas->tree)) {
+		/*
+		 * Expand the range, only partially overwriting the previous and
+		 * next ranges
+		 */
+		gap |= !mt_slot_locked(mas->tree, slots, offset + 2);
+		rcu_assign_pointer(slots[offset + 1], wr_mas->entry);
 		wr_mas->pivots[offset] = mas->index - 1;
+		wr_mas->pivots[offset + 1] = mas->last;
 		mas->offset++; /* Keep mas accurate. */
+	} else {
+		return false;
 	}
 
 	trace_ma_write(__func__, mas, 0, wr_mas->entry);
-- 
2.20.1

Re: [PATCH v3 4/4] maple_tree: add a fast path case in mas_wr_slot_store()

[Liam R. Howlett]

* Peng Zhang <zhangpeng.00@bytedance.com> [230615 04:43]:
> When expanding a range in two directions, only partially overwriting the
> previous and next ranges, the number of entries will not be increased, so
> we can just update the pivots as a fast path. However, it may introduce
> potential risks in RCU mode (although it may pass the test), because it
> updates two pivots. We only enable it in non-RCU mode for now.

You've fixed the above test passing without the RCU bit set, so this
comment should be removed.

> 
> Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com>
> ---
>  lib/maple_tree.c | 36 ++++++++++++++++++++++++------------
>  1 file changed, 24 insertions(+), 12 deletions(-)
> 
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index da4af6743b30..bff6531fd0bc 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -4100,23 +4100,35 @@ static inline bool mas_wr_slot_store(struct ma_wr_state *wr_mas)
>  {
>  	struct ma_state *mas = wr_mas->mas;
>  	unsigned char offset = mas->offset;
> +	void __rcu **slots = wr_mas->slots;
>  	bool gap = false;
>  
> -	if (wr_mas->offset_end - offset != 1)
> -		return false;
> -
> -	gap |= !mt_slot_locked(mas->tree, wr_mas->slots, offset);
> -	gap |= !mt_slot_locked(mas->tree, wr_mas->slots, offset + 1);
> +	gap |= !mt_slot_locked(mas->tree, slots, offset);
> +	gap |= !mt_slot_locked(mas->tree, slots, offset + 1);
>  
> -	if (mas->index == wr_mas->r_min) {
> -		/* Overwriting the range and over a part of the next range. */
> -		rcu_assign_pointer(wr_mas->slots[offset], wr_mas->entry);
> -		wr_mas->pivots[offset] = mas->last;
> -	} else {
> -		/* Overwriting a part of the range and over the next range */
> -		rcu_assign_pointer(wr_mas->slots[offset + 1], wr_mas->entry);
> +	if (wr_mas->offset_end - offset == 1) {
> +		if (mas->index == wr_mas->r_min) {
> +			/* Overwriting the range and a part of the next one */
> +			rcu_assign_pointer(slots[offset], wr_mas->entry);
> +			wr_mas->pivots[offset] = mas->last;
> +		} else {
> +			/* Overwriting a part of the range and the next one */
> +			rcu_assign_pointer(slots[offset + 1], wr_mas->entry);
> +			wr_mas->pivots[offset] = mas->index - 1;
> +			mas->offset++; /* Keep mas accurate. */
> +		}
> +	} else if (!mt_in_rcu(mas->tree)) {
> +		/*
> +		 * Expand the range, only partially overwriting the previous and
> +		 * next ranges
> +		 */
> +		gap |= !mt_slot_locked(mas->tree, slots, offset + 2);
> +		rcu_assign_pointer(slots[offset + 1], wr_mas->entry);
>  		wr_mas->pivots[offset] = mas->index - 1;
> +		wr_mas->pivots[offset + 1] = mas->last;
>  		mas->offset++; /* Keep mas accurate. */
> +	} else {
> +		return false;
>  	}
>  
>  	trace_ma_write(__func__, mas, 0, wr_mas->entry);
> -- 
> 2.20.1
> 

Re: [PATCH v3 0/4] Optimize the fast path of mas_store()

[Peng Zhang]

在 2023/6/15 16:42, Peng Zhang 写道:
> Add fast paths for mas_wr_append() and mas_wr_slot_store() respectively.
> The newly added fast path of mas_wr_append() is used in fork() and how
> much it benefits fork() depends on how many VMAs are duplicated.
> 
> Changes since v2:
>   - Add test for expanding range in RCU mode. [2/4]
> 
> v1: https://lore.kernel.org/lkml/20230602075353.5917-1-zhangpeng.00@bytedance.com/
> v2: https://lore.kernel.org/lkml/20230609120347.63936-1-zhangpeng.00@bytedance.com/
> 
> Peng Zhang (4):
>    maple_tree: add test for mas_wr_modify() fast path
>    maple_tree: add test for expanding range in RCU mode
>    maple_tree: optimize mas_wr_append(), also improve duplicating VMAs
>    maple_tree: add a fast path case in mas_wr_slot_store()
> 
>   lib/maple_tree.c                 | 69 +++++++++++++++++++----------
>   lib/test_maple_tree.c            | 65 +++++++++++++++++++++++++++
>   tools/testing/radix-tree/maple.c | 75 ++++++++++++++++++++++++++++++++
>   3 files changed, 186 insertions(+), 23 deletions(-)
> 
Hi Andrew,

I think this patchset can be queued for testing.
Both v2 and v3 just update the test code.

Re: [PATCH v3 0/4] Optimize the fast path of mas_store()

[Liam R. Howlett]

* Peng Zhang <zhangpeng.00@bytedance.com> [230615 04:43]:
> Add fast paths for mas_wr_append() and mas_wr_slot_store() respectively.
> The newly added fast path of mas_wr_append() is used in fork() and how
> much it benefits fork() depends on how many VMAs are duplicated.
> 
> Changes since v2:
>  - Add test for expanding range in RCU mode. [2/4]

Apologies for the late review, other tasks had me held up.

Dropping the RCU flag from your test makes your test fail as expected.
It also fails if we alter the code to not check the rcu flag.  So your
test works and I'm happy with your changes.

Please remove the statement from the change log in patch 4 regarding
testing since you have fixed testing and add:

Reviewed-by: Liam R. Howlett <Liam.Howlett@oracle.com>

For the whole patch series.


> 
> v1: https://lore.kernel.org/lkml/20230602075353.5917-1-zhangpeng.00@bytedance.com/
> v2: https://lore.kernel.org/lkml/20230609120347.63936-1-zhangpeng.00@bytedance.com/
> 
> Peng Zhang (4):
>   maple_tree: add test for mas_wr_modify() fast path
>   maple_tree: add test for expanding range in RCU mode
>   maple_tree: optimize mas_wr_append(), also improve duplicating VMAs
>   maple_tree: add a fast path case in mas_wr_slot_store()
> 
>  lib/maple_tree.c                 | 69 +++++++++++++++++++----------
>  lib/test_maple_tree.c            | 65 +++++++++++++++++++++++++++
>  tools/testing/radix-tree/maple.c | 75 ++++++++++++++++++++++++++++++++
>  3 files changed, 186 insertions(+), 23 deletions(-)
> 
> -- 
> 2.20.1
> 
>