| Message ID | 20231212194640.217966-1-sidhartha.kumar@oracle.com (mailing list archive) |
|---|---|
| State | New |
| Headers | show |
| Series | maple_tree: do not preallocate nodes for slot stores | expand |
* 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 >
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 <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
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 <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 --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);
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(-)