[v5,0/5] refine storing null

Message

Wei Yang Oct. 31, 2024, 11:16 p.m. UTC

The original thread[1] thoughts it is a problem in mas_new_root(). But after
discussion, this should be an improvement on storing NULL.

Patch 1/2 preparation for refine.

Patch 3 remove redundant check in mas_new_root().

Patch 4 refine mas_store_root() to improve memory efficiency and remove
possible consecutive NULL slot.

Patch 5 adds a test for storing NULL.

[1]: https://lkml.kernel.org/r/[e-mail]

v5:
  rebase on akpm mm-unstable
  fix a build warning on xa_is_node() in patch 5

v4:
  patch 3 add a WARN_ON_ONCE()
  patch 4 add a comment and simplify the logic a little

v3:
  patch 4 move the change into mas_store_root()
  patch 5 move test into lib/test_maple_tree.c

Wei Yang (5):
  maple_tree: print empty for an empty tree on mt_dump()
  maple_tree: the return value of mas_root_expand() is not used
  maple_tree: not necessary to check index/last again
  maple_tree: refine mas_store_root() on storing NULL
  maple_tree: add a test checking storing null

 lib/maple_tree.c      | 29 ++++++++++----
 lib/test_maple_tree.c | 90 +++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 112 insertions(+), 7 deletions(-)

Comments

Andrew Morton Nov. 1, 2024, 12:20 a.m. UTC | #1

On Thu, 31 Oct 2024 23:16:22 +0000 Wei Yang <[e-mail]> 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/[e-mail]

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?

Liam R. Howlett Nov. 1, 2024, 2:52 p.m. UTC | #2

* Andrew Morton <[e-mail]> [241101 09:54]:
> On Thu, 31 Oct 2024 23:16:22 +0000 Wei Yang <[e-mail]> 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/[e-mail]
> 
> 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

Wei Yang Nov. 3, 2024, 11:09 p.m. UTC | #3

On Fri, Nov 01, 2024 at 10:52:42AM -0400, Liam R. Howlett wrote:
>* Andrew Morton <[e-mail]> [241101 09:54]:
>> On Thu, 31 Oct 2024 23:16:22 +0000 Wei Yang <[e-mail]> 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/[e-mail]
>> 
>> 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.

Thanks for the detailed explanation.

>
>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.

I will be more careful for this next time.

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