[PATCH V2] maple_tree: do not preallocate nodes for slot stores

[PATCH V2] maple_tree: do not preallocate nodes for slot stores

[Sidhartha Kumar]

mas_preallocate() defaults to requesting 1 node for preallocation and then
,depending on the type of store, will update the request variable. There
isn't a check for a slot store type, so slot stores are preallocating the
default 1 node. Slot stores do not require any additional nodes, so add a
check for the slot store case that will bypass node_count_gfp(). Update
the tests to reflect that slot stores do not require allocations.

User visible effects of this bug include increased memory usage from the
unneeded node that was allocated.

Fixes: 0b8bb544b1a7 ("maple_tree: update mas_preallocate() testing")
Cc: <stable@vger.kernel.org> # 6.6+
Signed-off-by: Sidhartha Kumar <sidhartha.kumar@oracle.com>
---
v1->v2:
	fix coding style per Matthew and Andrew
	use wr_mas->node_end to fix build error


 lib/maple_tree.c                 | 11 +++++++++++
 tools/testing/radix-tree/maple.c |  2 +-
 2 files changed, 12 insertions(+), 1 deletion(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index bb24d84a4922f..684689457d77f 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -5501,6 +5501,17 @@ int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp)
 
 	mas_wr_end_piv(&wr_mas);
 	node_size = mas_wr_new_end(&wr_mas);
+
+	/* Slot store, does not require additional nodes */
+	if (node_size == wr_mas.node_end) {
+		/* reuse node */
+		if (!mt_in_rcu(mas->tree))
+			return 0;
+		/* shifting boundary */
+		if (wr_mas.offset_end - mas->offset == 1)
+			return 0;
+	}
+
 	if (node_size >= mt_slots[wr_mas.type]) {
 		/* Split, worst case for now. */
 		request = 1 + mas_mt_height(mas) * 2;
diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c
index e5da1cad70baf..76a8990bb14e8 100644
--- a/tools/testing/radix-tree/maple.c
+++ b/tools/testing/radix-tree/maple.c
@@ -35538,7 +35538,7 @@ static noinline void __init check_prealloc(struct maple_tree *mt)
 	MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
 	allocated = mas_allocated(&mas);
 	height = mas_mt_height(&mas);
-	MT_BUG_ON(mt, allocated != 1);
+	MT_BUG_ON(mt, allocated != 0);
 	mas_store_prealloc(&mas, ptr);
 	MT_BUG_ON(mt, mas_allocated(&mas) != 0);
 
-- 
2.42.0

Re: [PATCH V2] maple_tree: do not preallocate nodes for slot stores

[Sidhartha Kumar]

On 12/13/23 12:50 PM, Sidhartha Kumar wrote:
> mas_preallocate() defaults to requesting 1 node for preallocation and then
> ,depending on the type of store, will update the request variable. There
> isn't a check for a slot store type, so slot stores are preallocating the
> default 1 node. Slot stores do not require any additional nodes, so add a
> check for the slot store case that will bypass node_count_gfp(). Update
> the tests to reflect that slot stores do not require allocations.
> 
> User visible effects of this bug include increased memory usage from the
> unneeded node that was allocated.
> 
> Fixes: 0b8bb544b1a7 ("maple_tree: update mas_preallocate() testing")
> Cc: <stable@vger.kernel.org> # 6.6+
> Signed-off-by: Sidhartha Kumar <sidhartha.kumar@oracle.com>
> ---
> v1->v2:
> 	fix coding style per Matthew and Andrew
> 	use wr_mas->node_end to fix build error
> 

When this is merged to mm-unstable could the following fixlet be applied to be 
compatible with Liam's series[1]:

[1]: 
https://lore.kernel.org/all/20231101171629.3612299-5-Liam.Howlett@oracle.com/T/#mc0e5000f6de822182bf7579c230030c5ec4ec1a7

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 1130803b9d3f7..c9a970ea20dd5 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -5477,7 +5477,7 @@ int mas_preallocate(struct ma_state *mas, void *entry, 
gfp_t gfp)
         node_size = mas_wr_new_end(&wr_mas);

         /* Slot store, does not require additional nodes */
-       if (node_size == wr_mas.node_end) {
+       if (node_size == mas->end) {
                 /* reuse node */
                 if (!mt_in_rcu(mas->tree))
                         return 0;

> 
>   lib/maple_tree.c                 | 11 +++++++++++
>   tools/testing/radix-tree/maple.c |  2 +-
>   2 files changed, 12 insertions(+), 1 deletion(-)
> 
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index bb24d84a4922f..684689457d77f 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -5501,6 +5501,17 @@ int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp)
>   
>   	mas_wr_end_piv(&wr_mas);
>   	node_size = mas_wr_new_end(&wr_mas);
> +
> +	/* Slot store, does not require additional nodes */
> +	if (node_size == wr_mas.node_end) {
> +		/* reuse node */
> +		if (!mt_in_rcu(mas->tree))
> +			return 0;
> +		/* shifting boundary */
> +		if (wr_mas.offset_end - mas->offset == 1)
> +			return 0;
> +	}
> +
>   	if (node_size >= mt_slots[wr_mas.type]) {
>   		/* Split, worst case for now. */
>   		request = 1 + mas_mt_height(mas) * 2;
> diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c
> index e5da1cad70baf..76a8990bb14e8 100644
> --- a/tools/testing/radix-tree/maple.c
> +++ b/tools/testing/radix-tree/maple.c
> @@ -35538,7 +35538,7 @@ static noinline void __init check_prealloc(struct maple_tree *mt)
>   	MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
>   	allocated = mas_allocated(&mas);
>   	height = mas_mt_height(&mas);
> -	MT_BUG_ON(mt, allocated != 1);
> +	MT_BUG_ON(mt, allocated != 0);
>   	mas_store_prealloc(&mas, ptr);
>   	MT_BUG_ON(mt, mas_allocated(&mas) != 0);
>   

Re: [PATCH V2] maple_tree: do not preallocate nodes for slot stores

[Andrew Morton]

On Wed, 13 Dec 2023 13:03:29 -0800 Sidhartha Kumar <sidhartha.kumar@oracle.com> wrote:

> On 12/13/23 12:50 PM, Sidhartha Kumar wrote:
> > mas_preallocate() defaults to requesting 1 node for preallocation and then
> > ,depending on the type of store, will update the request variable. There
> > isn't a check for a slot store type, so slot stores are preallocating the
> > default 1 node. Slot stores do not require any additional nodes, so add a
> > check for the slot store case that will bypass node_count_gfp(). Update
> > the tests to reflect that slot stores do not require allocations.
> > 
> > User visible effects of this bug include increased memory usage from the
> > unneeded node that was allocated.
> > 
> > Fixes: 0b8bb544b1a7 ("maple_tree: update mas_preallocate() testing")
> > Cc: <stable@vger.kernel.org> # 6.6+
> > Signed-off-by: Sidhartha Kumar <sidhartha.kumar@oracle.com>
> > ---
> > v1->v2:
> > 	fix coding style per Matthew and Andrew
> > 	use wr_mas->node_end to fix build error
> > 
> 
> When this is merged to mm-unstable could the following fixlet be applied to be 
> compatible with Liam's series[1]:
> 

Yup, already on it.  Liam's series is now in mm-stable so for now I'll
leave a bisection hole.  Maybe I'll fold it later if an mm-stable
rebase/rebuild is needed,

From: Andrew Morton <akpm@linux-foundation.org>
Subject: lib/maple_tree.c: fix build error due to hotfix alteration
Date: Wed Dec 13 12:59:49 PM PST 2023

Commit 0de56e38b307 ("maple_tree: use maple state end for write
operations") was broken by a later patch "maple_tree: do not preallocate
nodes for slot stores".  But the later patch was scheduled ahead of
0de56e38b307, for 6.7-rc.

This fixlet undoes the damage.

Fixes: 0de56e38b307 ("maple_tree: use maple state end for write operations")
Cc: Liam R. Howlett <Liam.Howlett@oracle.com>
Cc: Sidhartha Kumar <sidhartha.kumar@oracle.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
---

 lib/maple_tree.c |    2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

--- a/lib/maple_tree.c~lib-maple_treec-fix-build-error-due-to-hotfix-alteration
+++ a/lib/maple_tree.c
@@ -5477,7 +5477,7 @@ int mas_preallocate(struct ma_state *mas
 	node_size = mas_wr_new_end(&wr_mas);
 
 	/* Slot store, does not require additional nodes */
-	if (node_size == wr_mas.node_end) {
+	if (node_size == mas->end) {
 		/* reuse node */
 		if (!mt_in_rcu(mas->tree))
 			return 0;
_