| Message ID | 20241031231627.14316-5-richard.weiyang@gmail.com (mailing list archive) |
|---|---|
| State | New |
| Headers | show |
| Series | refine storing null | expand |
* Wei Yang <richard.weiyang@gmail.com> [241031 19:17]: > Currently, when storing NULL on mas_store_root(), the behavior could be > improved. Storing NULLs over the entire tree may result in a node being used to store a single range. Further stores of NULL may cause the node and tree to be corrupt and cause incorrect behaviour. Fixing the store to the root null fixes the issue by ensuring that a range of 0 - ULONG_MAX results in an empty tree. Users of the tree may experience incorrect values returned if the tree was expanded to store values, then overwritten by all NULLS, then continued to store NULLs over the empty area. > > 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 > * it allows for multiple NULL entries by expanding root > to store NULLs to an empty tree > > 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> > Reviewed-by: Liam R. Howlett <Liam.Howlett@Oracle.com> Please add stable to Cc list, and fixes tag. This needs to be backported, probably to v6.1 > > --- > v3: move change into mas_store_root() > v4: add a comment and simplify the logic a little > adjust the change log a little > --- > lib/maple_tree.c | 13 ++++++++++++- > 1 file changed, 12 insertions(+), 1 deletion(-) > > diff --git a/lib/maple_tree.c b/lib/maple_tree.c > index 4900f182e99d..d0ae808f3a14 100644 > --- a/lib/maple_tree.c > +++ b/lib/maple_tree.c > @@ -3447,9 +3447,20 @@ static inline void mas_root_expand(struct ma_state *mas, void *entry) > return; > } > > +/* > + * mas_store_root() - Storing value into root. > + * @mas: The maple state > + * @entry: The entry to store. > + * > + * There is no root node now and we are storing a value into the root - this > + * function either assigns the pointer or expands into a node. > + */ > static inline void mas_store_root(struct ma_state *mas, void *entry) > { > - if (likely((mas->last != 0) || (mas->index != 0))) > + if (!entry) { > + if (!mas->index) > + rcu_assign_pointer(mas->tree->ma_root, NULL); > + } else if (likely((mas->last != 0) || (mas->index != 0))) > mas_root_expand(mas, entry); > else if (((unsigned long) (entry) & 3) == 2) > mas_root_expand(mas, entry); > -- > 2.34.1 >
On Fri, 1 Nov 2024 10:59:24 -0400 "Liam R. Howlett" <Liam.Howlett@oracle.com> wrote: > * Wei Yang <richard.weiyang@gmail.com> [241031 19:17]: > > Currently, when storing NULL on mas_store_root(), the behavior could be > > improved. > > Storing NULLs over the entire tree may result in a node being used to > store a single range. Further stores of NULL may cause the node and > tree to be corrupt and cause incorrect behaviour. Fixing the store to > the root null fixes the issue by ensuring that a range of 0 - ULONG_MAX > results in an empty tree. > > Users of the tree may experience incorrect values returned if the tree > was expanded to store values, then overwritten by all NULLS, then > continued to store NULLs over the empty area. I pasted that into the changelog. > > > > 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 > > * it allows for multiple NULL entries by expanding root > > to store NULLs to an empty tree > > > > 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> > > Reviewed-by: Liam R. Howlett <Liam.Howlett@Oracle.com> > > Please add stable to Cc list, and fixes tag. This needs to be > backported, probably to v6.1 I added Fixes: 54a611b60590 ("Maple Tree: add new data structure") Cc: <stable@vger.kernel.org>
diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 4900f182e99d..d0ae808f3a14 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -3447,9 +3447,20 @@ static inline void mas_root_expand(struct ma_state *mas, void *entry) return; } +/* + * mas_store_root() - Storing value into root. + * @mas: The maple state + * @entry: The entry to store. + * + * There is no root node now and we are storing a value into the root - this + * function either assigns the pointer or expands into a node. + */ static inline void mas_store_root(struct ma_state *mas, void *entry) { - if (likely((mas->last != 0) || (mas->index != 0))) + if (!entry) { + if (!mas->index) + rcu_assign_pointer(mas->tree->ma_root, NULL); + } else if (likely((mas->last != 0) || (mas->index != 0))) mas_root_expand(mas, entry); else if (((unsigned long) (entry) & 3) == 2) mas_root_expand(mas, entry);
Currently, when storing NULL on mas_store_root(), 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 * it allows for multiple NULL entries by expanding root to store NULLs to an empty tree 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> Reviewed-by: Liam R. Howlett <Liam.Howlett@Oracle.com> --- v3: move change into mas_store_root() v4: add a comment and simplify the logic a little adjust the change log a little --- lib/maple_tree.c | 13 ++++++++++++- 1 file changed, 12 insertions(+), 1 deletion(-)