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 <[email protected]>
---
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
* Sidhartha Kumar <[email protected]> [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 <[email protected]>
Reviewed-by: Liam R. Howlett <[email protected]>
> ---
> 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
>
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.
* Matthew Wilcox <[email protected]> [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
> [email protected]
> https://lists.infradead.org/mailman/listinfo/maple-tree
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.
>
On Tue, 12 Dec 2023 20:57:48 +0000 Matthew Wilcox <[email protected]> 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.