[PATCH v5 0/5] refine storing null

[Liam R. Howlett]

* Andrew Morton <akpm at linux-foundation.org> [241101 09:54]:
> On Thu, 31 Oct 2024 23:16:22 +0000 Wei Yang <richard.weiyang at gmail.com> wrote:
> 
> > The original thread[1] thoughts it is a problem in mas_new_root(). But after
> > discussion, this should be an improvement on storing NULL.
> 
> I hate to be a bureaucrat, but that isn't a very satisfying [0/N].
> 
> > 
> > [1]: https://lkml.kernel.org/r/20241015233909.23592-1-richard.weiyang@gmail.com
> 
> From here I extracted "When overwriting the whole range with NULL,
> current behavior is not correct", but that's still very thin.  What is
> incorrect about it and what is the impact of all of this to Linux users?
> 

An empty tree is represented by having the tree point to NULL directly.
An empty tree indicates the entire range (0-ULONG_MAX) is NULL.

A store operation into an existing node that causes 0 - ULONG_MAX to be
equal to NULL may not be restored to an empty state - a node is used to
store the single range instead.  This is wasteful and different from the
initial setup of the tree.

Once the tree is using a single node to store 0 - ULONG_MAX, problems
may arise when storing more values into a tree with the unexpected state
of 0 - ULONG being a single range in a node.

User visible issues may mean a corrupt tree and incorrect storage of
information within the tree.  This would be limited to users who create
and then empty a tree by overwriting all values, then try to store more
NULLs into the empty tree.

I cannot come up with an example of any user doing this (users usually
destroy the tree and generally don't keep trying to store NULLs over
NULLs), but patch 4/5 "maple_tree: refine mas_store_root() on storing
NULL" should be backported just in case.

I said patch 4/5 needed to be backported in v3 [1], but stable didn't
get added to the Cc list and I missed it on review of v4.  I added to
the confusion by stating in an earlier version that it did not need to
be backported [2].  At the time the issue of corrupting the node wasn't
in the description. It should go back to v6.1.

I will be more clear in my communication on Cc'ing stable in the future.
The description of 4/5 is inadequate and I'll respond there as well.

[1] https://lore.kernel.org/all/jo4wjti235pqmzd6qaziexzjsavt53vmtyzyvw4htrcwpuxf4n@ctyucxk5avrc/
[2] https://lore.kernel.org/all/ia7qdjv5c5hmg6yds3tz2x5to5u65k47ssgudiayxjqrowu4fm@i5la2j7kpe5k/

Thanks,
Liam