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

[PATCH] 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")
Signed-off-by: Sidhartha Kumar <sidhartha.kumar@oracle.com>
---
This patch passes the maple tree test suite. A seperate patch will be sent
for a 6.6 stable backport as the node_end field was moved from the
ma_wr_state to the ma_state in a recent patch which is not in 6.6.


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

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index e6954fa75eb5..e4a39beb1018 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -5475,6 +5475,12 @@ 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 == mas->end) && ((!mt_in_rcu(mas->tree))
+		|| (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 687886cebd9d..f1caf4bcf937 100644
--- a/tools/testing/radix-tree/maple.c
+++ b/tools/testing/radix-tree/maple.c
@@ -35545,7 +35545,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] maple_tree: do not preallocate nodes for slot stores

[Liam R. Howlett]

* Sidhartha Kumar <sidhartha.kumar@oracle.com> [231212 14:46]:
> 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")
> Signed-off-by: Sidhartha Kumar <sidhartha.kumar@oracle.com>

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

> ---
> This patch passes the maple tree test suite. A seperate patch will be sent
> for a 6.6 stable backport as the node_end field was moved from the
> ma_wr_state to the ma_state in a recent patch which is not in 6.6.
> 
> 
>  lib/maple_tree.c                 | 6 ++++++
>  tools/testing/radix-tree/maple.c | 2 +-
>  2 files changed, 7 insertions(+), 1 deletion(-)
> 
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index e6954fa75eb5..e4a39beb1018 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -5475,6 +5475,12 @@ 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 == mas->end) && ((!mt_in_rcu(mas->tree))
> +		|| (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 687886cebd9d..f1caf4bcf937 100644
> --- a/tools/testing/radix-tree/maple.c
> +++ b/tools/testing/radix-tree/maple.c
> @@ -35545,7 +35545,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] maple_tree: do not preallocate nodes for slot stores

[Matthew Wilcox]

On Tue, Dec 12, 2023 at 11:46:40AM -0800, Sidhartha Kumar wrote:
> +	/* Slot store, does not require additional nodes */
> +	if ((node_size == mas->end) && ((!mt_in_rcu(mas->tree))
> +		|| (wr_mas.offset_end - mas->offset == 1)))
> +		return 0;

Should we refactor this into a mas_is_slot_store() predicate?

A few coding-style problems with it as it's currently written:

1. The indentation on the second line is wrong.  It makes the
continuation of the condition look like part of the statement.  Use
extra whitespace to indent.  eg:

	if ((node_size == mas->end) && ((!mt_in_rcu(mas->tree))
			|| (wr_mas.offset_end - mas->offset == 1)))
		return 0;

2. The operator goes last on the line, not at the beginning of the
continuation line.  ie:

	if ((node_size == mas->end) && ((!mt_in_rcu(mas->tree)) ||
			(wr_mas.offset_end - mas->offset == 1)))
		return 0;

3. You don't need parens around the !mt_in_rcu(mas->tree).  There's
no ambiguity to solve here:

	if ((node_size == mas->end) && (!mt_in_rcu(mas->tree) ||
			(wr_mas.offset_end - mas->offset == 1)))
		return 0;

But I'd write it as:

	if ((node_size == mas->end) &&
	    (!mt_in_rcu(mas->tree) || (wr_mas.offset_end - mas->offset == 1)))
		return 0;

because then the whitespace matches how you're supposed to parse the
condition, and so the next person to read this code will have an easier
time of it.

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

[Liam R. Howlett]

* Matthew Wilcox <willy@infradead.org> [231212 15:58]:
> On Tue, Dec 12, 2023 at 11:46:40AM -0800, Sidhartha Kumar wrote:
> > +	/* Slot store, does not require additional nodes */
> > +	if ((node_size == mas->end) && ((!mt_in_rcu(mas->tree))
> > +		|| (wr_mas.offset_end - mas->offset == 1)))
> > +		return 0;
> 
> Should we refactor this into a mas_is_slot_store() predicate?

I'm not sure it's worth it as some of these are deciding factors on how
the store is executed so I would expect this to live in a single place,
long term.

Although, long-term this could be two store types: slot store rcu and
slot store so that the check only happens once.

> 
> A few coding-style problems with it as it's currently written:
> 
> 1. The indentation on the second line is wrong.  It makes the
> continuation of the condition look like part of the statement.  Use
> extra whitespace to indent.  eg:
> 
> 	if ((node_size == mas->end) && ((!mt_in_rcu(mas->tree))
> 			|| (wr_mas.offset_end - mas->offset == 1)))
> 		return 0;
> 
> 2. The operator goes last on the line, not at the beginning of the
> continuation line.  ie:
> 
> 	if ((node_size == mas->end) && ((!mt_in_rcu(mas->tree)) ||
> 			(wr_mas.offset_end - mas->offset == 1)))
> 		return 0;
> 
> 3. You don't need parens around the !mt_in_rcu(mas->tree).  There's
> no ambiguity to solve here:
> 
> 	if ((node_size == mas->end) && (!mt_in_rcu(mas->tree) ||
> 			(wr_mas.offset_end - mas->offset == 1)))
> 		return 0;
> 
> But I'd write it as:
> 
> 	if ((node_size == mas->end) &&
> 	    (!mt_in_rcu(mas->tree) || (wr_mas.offset_end - mas->offset == 1)))
> 		return 0;
> 
> because then the whitespace matches how you're supposed to parse the
> condition, and so the next person to read this code will have an easier
> time of it.
> 
> 
> -- 
> maple-tree mailing list
> maple-tree@lists.infradead.org
> https://lists.infradead.org/mailman/listinfo/maple-tree

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

[Sidhartha Kumar]

On 12/12/23 12:57 PM, Matthew Wilcox wrote:
> On Tue, Dec 12, 2023 at 11:46:40AM -0800, Sidhartha Kumar wrote:
>> +	/* Slot store, does not require additional nodes */
>> +	if ((node_size == mas->end) && ((!mt_in_rcu(mas->tree))
>> +		|| (wr_mas.offset_end - mas->offset == 1)))
>> +		return 0;
> 
> Should we refactor this into a mas_is_slot_store() predicate?
  yes, I think we should add helper functions to identify the different type of 
stores. Thanks for the pointers to code style this is what I think the slot 
store identifying helper function would look like:

static inline bool mas_wr_is_slot_store(struct ma_wr_state *wr_mas)
{
	struct ma_state *mas = wr_mas->mas;
	unsigned char node_size = mas_wr_new_end(wr_mas);

	if ((node_size == mas->end) &&
	    (!mt_in_rcu(mas->tree) || (wr_mas->offset_end - mas->offset == 1)))
		return true;

	return false;
}

thanks,
Sid
> A few coding-style problems with it as it's currently written:
> 
> 1. The indentation on the second line is wrong.  It makes the
> continuation of the condition look like part of the statement.  Use
> extra whitespace to indent.  eg:
> 
> 	if ((node_size == mas->end) && ((!mt_in_rcu(mas->tree))
> 			|| (wr_mas.offset_end - mas->offset == 1)))
> 		return 0;
> 
> 2. The operator goes last on the line, not at the beginning of the
> continuation line.  ie:
> 
> 	if ((node_size == mas->end) && ((!mt_in_rcu(mas->tree)) ||
> 			(wr_mas.offset_end - mas->offset == 1)))
> 		return 0;
> 
> 3. You don't need parens around the !mt_in_rcu(mas->tree).  There's
> no ambiguity to solve here:
> 
> 	if ((node_size == mas->end) && (!mt_in_rcu(mas->tree) ||
> 			(wr_mas.offset_end - mas->offset == 1)))
> 		return 0;
> 
> But I'd write it as:
> 
> 	if ((node_size == mas->end) &&
> 	    (!mt_in_rcu(mas->tree) || (wr_mas.offset_end - mas->offset == 1)))
> 		return 0;
> 
> because then the whitespace matches how you're supposed to parse the
> condition, and so the next person to read this code will have an easier
> time of it.
> 

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

[Andrew Morton]

On Tue, 12 Dec 2023 20:57:48 +0000 Matthew Wilcox <willy@infradead.org> wrote:

> On Tue, Dec 12, 2023 at 11:46:40AM -0800, Sidhartha Kumar wrote:
> > +	/* Slot store, does not require additional nodes */
> > +	if ((node_size == mas->end) && ((!mt_in_rcu(mas->tree))
> > +		|| (wr_mas.offset_end - mas->offset == 1)))
> > +		return 0;
> 
> Should we refactor this into a mas_is_slot_store() predicate?
> 
> A few coding-style problems with it as it's currently written:
> 
> 1. The indentation on the second line is wrong.  It makes the
> continuation of the condition look like part of the statement.  Use
> extra whitespace to indent.  eg:
> 
> 	if ((node_size == mas->end) && ((!mt_in_rcu(mas->tree))
> 			|| (wr_mas.offset_end - mas->offset == 1)))
> 		return 0;
> 
> 2. The operator goes last on the line, not at the beginning of the
> continuation line.  ie:
> 
> 	if ((node_size == mas->end) && ((!mt_in_rcu(mas->tree)) ||
> 			(wr_mas.offset_end - mas->offset == 1)))
> 		return 0;
> 
> 3. You don't need parens around the !mt_in_rcu(mas->tree).  There's
> no ambiguity to solve here:
> 
> 	if ((node_size == mas->end) && (!mt_in_rcu(mas->tree) ||
> 			(wr_mas.offset_end - mas->offset == 1)))
> 		return 0;
> 
> But I'd write it as:
> 
> 	if ((node_size == mas->end) &&
> 	    (!mt_in_rcu(mas->tree) || (wr_mas.offset_end - mas->offset == 1)))
> 		return 0;
> 
> because then the whitespace matches how you're supposed to parse the
> condition, and so the next person to read this code will have an easier
> time of it.

Yup.  But I'd suggest going further:

	/* Slot store, does not require additional nodes */
	if (node_size == mas->end) {
		/* comment goes here */
		if (!mt_in_rcu(mas->tree))
			return 0;
		/* and here too */
		if (wr_mas.offset_end - mas->offset == 1)
			return 0;
	}

ie: create space to add those comments explaining the reason for each test.