[PATCH v5 4/5] maple_tree: refine mas_store_root() on storing NULL

[Andrew Morton]

On Fri, 1 Nov 2024 10:59:24 -0400 "Liam R. Howlett" <Liam.Howlett at oracle.com> wrote:

> * Wei Yang <richard.weiyang at 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 at gmail.com>
> > CC: Liam R. Howlett <Liam.Howlett at Oracle.com>
> > CC: Sidhartha Kumar <sidhartha.kumar at oracle.com>
> > CC: Lorenzo Stoakes <lorenzo.stoakes at oracle.com>
> > Reviewed-by: Liam R. Howlett <Liam.Howlett at 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 at vger.kernel.org>