| Message ID | 20241017134607.30206-5-richard.weiyang@gmail.com (mailing list archive) |
|---|---|
| State | New |
| Headers | show |
| Series | refine storing NULL | expand |
* Wei Yang <richard.weiyang@gmail.com> [241017 09:46]: > Currently, when storing NULL on mas_root_expand(), the behavior could be > improved. > > For example possible cases are: > > * store NULL at any range result a new node > * store NULL at range [m, n] where m > 0 to a single entry tree result > a new node with range [m, n] set to NULL > * store NULL at range [m, n] where m > 0 to an empty tree result > consecutive NULL slot > > This patch tries to improve in: > > * memory efficient by setting to empty tree instead of using a node > * remove the possibility of consecutive NULL slot which will prohibit > extended null in later operation > > Signed-off-by: Wei Yang <richard.weiyang@gmail.com> > CC: Liam R. Howlett <Liam.Howlett@Oracle.com> > CC: Sidhartha Kumar <sidhartha.kumar@oracle.com> > CC: Lorenzo Stoakes <lorenzo.stoakes@oracle.com> > --- > lib/maple_tree.c | 18 ++++++++++++++++++ > 1 file changed, 18 insertions(+) > > diff --git a/lib/maple_tree.c b/lib/maple_tree.c > index a90c29156fe2..15d2124acc36 100644 > --- a/lib/maple_tree.c > +++ b/lib/maple_tree.c > @@ -3335,6 +3335,24 @@ static inline void mas_root_expand(struct ma_state *mas, void *entry) > unsigned long *pivots; > int slot = 0; > > + if (!entry) { > + /* > + * We come here in two cases: > + * 1. This is an empty tree > + * 2. This is a single entry tree with range [0, 0] > + * > + * If this is an empty tree, the result should still be an > + * empty tree no matter what the range is. > + * > + * If this is a single entry tree, we should set it to an > + * empty tree if the range cover [0, 0]. Otherwise, we don't > + * need to change it. > + */ > + if (!mas->index && contents) > + rcu_assign_pointer(mas->tree->ma_root, NULL); > + return; > + } > + This fix should be done in mas_store_root(), which will probably reduce or remove your lengthy comment. mas_root_expand() should... expand the root, and this isn't what is happening now. > node = mas_pop_node(mas); > pivots = ma_pivots(node, type); > slots = ma_slots(node, type); > -- > 2.34.1 >
On Thu, Oct 17, 2024 at 10:10:20AM -0400, Liam R. Howlett wrote: >* Wei Yang <richard.weiyang@gmail.com> [241017 09:46]: >> Currently, when storing NULL on mas_root_expand(), the behavior could be >> improved. >> >> For example possible cases are: >> >> * store NULL at any range result a new node >> * store NULL at range [m, n] where m > 0 to a single entry tree result >> a new node with range [m, n] set to NULL >> * store NULL at range [m, n] where m > 0 to an empty tree result >> consecutive NULL slot >> >> This patch tries to improve in: >> >> * memory efficient by setting to empty tree instead of using a node >> * remove the possibility of consecutive NULL slot which will prohibit >> extended null in later operation >> >> Signed-off-by: Wei Yang <richard.weiyang@gmail.com> >> CC: Liam R. Howlett <Liam.Howlett@Oracle.com> >> CC: Sidhartha Kumar <sidhartha.kumar@oracle.com> >> CC: Lorenzo Stoakes <lorenzo.stoakes@oracle.com> >> --- >> lib/maple_tree.c | 18 ++++++++++++++++++ >> 1 file changed, 18 insertions(+) >> >> diff --git a/lib/maple_tree.c b/lib/maple_tree.c >> index a90c29156fe2..15d2124acc36 100644 >> --- a/lib/maple_tree.c >> +++ b/lib/maple_tree.c >> @@ -3335,6 +3335,24 @@ static inline void mas_root_expand(struct ma_state *mas, void *entry) >> unsigned long *pivots; >> int slot = 0; >> >> + if (!entry) { >> + /* >> + * We come here in two cases: >> + * 1. This is an empty tree >> + * 2. This is a single entry tree with range [0, 0] >> + * >> + * If this is an empty tree, the result should still be an >> + * empty tree no matter what the range is. >> + * >> + * If this is a single entry tree, we should set it to an >> + * empty tree if the range cover [0, 0]. Otherwise, we don't >> + * need to change it. >> + */ >> + if (!mas->index && contents) >> + rcu_assign_pointer(mas->tree->ma_root, NULL); >> + return; >> + } >> + > >This fix should be done in mas_store_root(), which will probably reduce >or remove your lengthy comment. > >mas_root_expand() should... expand the root, and this isn't what is >happening now. > Right, will move it. Thanks >> node = mas_pop_node(mas); >> pivots = ma_pivots(node, type); >> slots = ma_slots(node, type); >> -- >> 2.34.1 >>
diff --git a/lib/maple_tree.c b/lib/maple_tree.c index a90c29156fe2..15d2124acc36 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -3335,6 +3335,24 @@ static inline void mas_root_expand(struct ma_state *mas, void *entry) unsigned long *pivots; int slot = 0; + if (!entry) { + /* + * We come here in two cases: + * 1. This is an empty tree + * 2. This is a single entry tree with range [0, 0] + * + * If this is an empty tree, the result should still be an + * empty tree no matter what the range is. + * + * If this is a single entry tree, we should set it to an + * empty tree if the range cover [0, 0]. Otherwise, we don't + * need to change it. + */ + if (!mas->index && contents) + rcu_assign_pointer(mas->tree->ma_root, NULL); + return; + } + node = mas_pop_node(mas); pivots = ma_pivots(node, type); slots = ma_slots(node, type);
Currently, when storing NULL on mas_root_expand(), the behavior could be improved. For example possible cases are: * store NULL at any range result a new node * store NULL at range [m, n] where m > 0 to a single entry tree result a new node with range [m, n] set to NULL * store NULL at range [m, n] where m > 0 to an empty tree result consecutive NULL slot This patch tries to improve in: * memory efficient by setting to empty tree instead of using a node * remove the possibility of consecutive NULL slot which will prohibit extended null in later operation Signed-off-by: Wei Yang <richard.weiyang@gmail.com> CC: Liam R. Howlett <Liam.Howlett@Oracle.com> CC: Sidhartha Kumar <sidhartha.kumar@oracle.com> CC: Lorenzo Stoakes <lorenzo.stoakes@oracle.com> --- lib/maple_tree.c | 18 ++++++++++++++++++ 1 file changed, 18 insertions(+)