diff mbox series

maple_tree: do not preallocate nodes for slot stores

Message ID 20231212194640.217966-1-sidhartha.kumar@oracle.com
State New
Headers
Series maple_tree: do not preallocate nodes for slot stores |

Commit Message

Sidhartha Kumar Dec. 12, 2023, 7:46 p.m. UTC 
  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(-)

Comments

Liam R. Howlett Dec. 12, 2023, 8:27 p.m. UTC | #1 
* 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
>
Matthew Wilcox Dec. 12, 2023, 8:57 p.m. UTC | #2 
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.
Liam R. Howlett Dec. 12, 2023, 9:41 p.m. UTC | #3 
* 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
Sidhartha Kumar Dec. 12, 2023, 9:48 p.m. UTC | #4 
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.
>
Andrew Morton Dec. 13, 2023, 1 a.m. UTC | #5 
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.
diff mbox series

Patch

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);