linux.git/lib/maple_tree.c, branch v6.6-rc2

maple_tree: clean up mas_wr_append()

2023-08-24T23:20:32+00:00

Avoid setting the variables until necessary, and actually use the
variables where applicable.  Introducing a variable for the slots array
avoids spanning multiple lines.

Add the missing argument to the documentation.

Use the node type when setting the metadata instead of blindly assuming
the type.

Finally, add a trace point to the function for successful store.

Link: https://lkml.kernel.org/r/20230819004356.1454718-3-Liam.Howlett@oracle.com
Signed-off-by: Liam R. Howlett 
Signed-off-by: Andrew Morton

merge mm-hotfixes-stable into mm-stable to pick up depended-upon changes

2023-08-24T22:25:56+00:00

maple_tree: disable mas_wr_append() when other readers are possible

2023-08-24T21:59:47+00:00

The current implementation of append may cause duplicate data and/or
incorrect ranges to be returned to a reader during an update.  Although
this has not been reported or seen, disable the append write operation
while the tree is in rcu mode out of an abundance of caution.

During the analysis of the mas_next_slot() the following was
artificially created by separating the writer and reader code:

Writer:                                 reader:
mas_wr_append
    set end pivot
    updates end metata
    Detects write to last slot
    last slot write is to start of slot
    store current contents in slot
    overwrite old end pivot
                                        mas_next_slot():
                                                read end metadata
                                                read old end pivot
                                                return with incorrect range
    store new value

Alternatively:

Writer:                                 reader:
mas_wr_append
    set end pivot
    updates end metata
    Detects write to last slot
    last lost write to end of slot
    store value
                                        mas_next_slot():
                                                read end metadata
                                                read old end pivot
                                                read new end pivot
                                                return with incorrect range
    set old end pivot

There may be other accesses that are not safe since we are now updating
both metadata and pointers, so disabling append if there could be rcu
readers is the safest action.

Link: https://lkml.kernel.org/r/20230819004356.1454718-2-Liam.Howlett@oracle.com
Fixes: 54a611b60590 ("Maple Tree: add new data structure")
Signed-off-by: Liam R. Howlett 
Cc: 
Signed-off-by: Andrew Morton

maple_tree: replace data before marking dead in split and spanning store

2023-08-21T20:37:41+00:00

Reorder the operations for split and spanning stores so that new data is
placed in the tree prior to marking the old data as dead.  This will limit
re-walks on dead data to just once instead of a retry loop.

The order of operations is as follows: Create the new data, put the new
data in place, mark the top node of the old data as dead.

Then repair parent links in the reused nodes through all levels of the
tree, following the new nodes downwards.  Finally walk the top dead node
looking for nodes that are no longer used, or subtrees that should be
destroyed (marked dead throughout then freed), follow the partially used
nodes downwards to discover other dead nodes and subtrees.

Link: https://lkml.kernel.org/r/20230804165951.2661157-7-Liam.Howlett@oracle.com
Signed-off-by: Liam R. Howlett 
Cc: Matthew Wilcox (Oracle) 
Cc: Paul E. McKenney 
Cc: Suren Baghdasaryan 
Signed-off-by: Andrew Morton

maple_tree: change mas_adopt_children() parent usage

2023-08-21T20:37:41+00:00

All calls to mas_adopt_children() currently pass the parent as the node in
the maple state.  Allow for the parent pointer that is passed in to be
used instead.

Link: https://lkml.kernel.org/r/20230804165951.2661157-6-Liam.Howlett@oracle.com
Signed-off-by: Liam R. Howlett 
Cc: Matthew Wilcox (Oracle) 
Cc: Paul E. McKenney 
Cc: Suren Baghdasaryan 
Signed-off-by: Andrew Morton

maple_tree: introduce mas_tree_parent() definition

2023-08-21T20:37:41+00:00

Add a definition to shorten long code lines and clarify what the code is
doing.  Use the new definition to get the maple tree parent pointer from
the maple state where possible.

Link: https://lkml.kernel.org/r/20230804165951.2661157-5-Liam.Howlett@oracle.com
Signed-off-by: Liam R. Howlett 
Cc: Matthew Wilcox (Oracle) 
Cc: Paul E. McKenney 
Cc: Suren Baghdasaryan 
Signed-off-by: Andrew Morton

maple_tree: introduce mas_put_in_tree()

2023-08-21T20:37:41+00:00

mas_replace() has a single user that takes a flag which is now always
true.  Replace this function with mas_put_in_tree() to better align with
mas_replace_node().  Inline the remaining logic into the only caller;
mas_wmb_replace().

Link: https://lkml.kernel.org/r/20230804165951.2661157-4-Liam.Howlett@oracle.com
Signed-off-by: Liam R. Howlett 
Cc: Matthew Wilcox (Oracle) 
Cc: Paul E. McKenney 
Cc: Suren Baghdasaryan 
Signed-off-by: Andrew Morton

maple_tree: reorder replacement of nodes to avoid live lock

2023-08-21T20:37:41+00:00

Replacing nodes may cause a live lock-up if CPU resources are saturated by
write operations on the tree by continuously retrying on dead nodes.  To
avoid the continuous retry scenario, ensure the new node is inserted into
the tree prior to marking the old data as dead.  This will define a window
where old and new data is swapped.

When reusing lower level nodes, ensure the parent pointer is updated after
the parent is marked dead.  This ensures that the child is still reachable
from the top of the tree, but walking up to a dead node will result in a
single retry that will start a fresh walk from the top down through the
new node.

Link: https://lkml.kernel.org/r/20230804165951.2661157-3-Liam.Howlett@oracle.com
Signed-off-by: Liam R. Howlett 
Cc: Matthew Wilcox (Oracle) 
Cc: Paul E. McKenney 
Cc: Suren Baghdasaryan 
Signed-off-by: Andrew Morton

maple_tree: add hex output to maple_arange64 dump

2023-08-21T20:37:40+00:00

Patch series "maple_tree: Change replacement strategy".

The maple tree marks nodes dead as soon as they are going to be replaced. 
This could be problematic when used in the RCU context since the writer
may be starved of CPU time by the readers.  This patch set addresses the
issue by switching the data replacement strategy to one that will only
mark data as dead once the new data is available.

This series changes the ordering of the node replacement so that the new
data is live before the old data is marked 'dead'.  When readers hit
'dead' nodes, they will restart from the top of the tree and end up in the
new data.

In more complex scenarios, the replacement strategy means a subtree is
built and graphed into the tree leaving some nodes to point to the old
parent.  The view of tasks into the old data will either remain with the
old data, or see the new data once the old data is marked 'dead'.

Iterators will see the 'dead' node and restart on their own and switch to
the new data.  There is no risk of the reader seeing old data in these
cases.

The 'dead' subtree of data is then fully marked dead, but reused nodes
will still point to the dead nodes until the parent pointer is updated. 
Walking up to a 'dead' node will cause a re-walk from the top of the tree
and enter the new data area where old data is not reachable.

Once the parent pointers are fully up to date in the active data, the
'dead' subtree is iterated to collect entirely 'dead' subtrees, and dead
nodes (nodes that partially contained reused data).


This patch (of 6):

When dumping the tree, honour formatting request to output hex for the
maple node type arange64.

Link: https://lkml.kernel.org/r/20230804165951.2661157-1-Liam.Howlett@oracle.com
Link: https://lkml.kernel.org/r/20230804165951.2661157-2-Liam.Howlett@oracle.com
Signed-off-by: Liam R. Howlett 
Cc: Matthew Wilcox (Oracle) 
Cc: Paul E. McKenney 
Cc: Suren Baghdasaryan 
Signed-off-by: Andrew Morton

maple_tree: reduce resets during store setup

2023-08-18T17:12:50+00:00

mas_prealloc() may walk partially down the tree before finding that a
split or spanning store is needed.  When the write occurs, relax the
logic on resetting the walk so that partial walks will not restart, but
walks that have gone too far (a store that affects beyond the current
node) should be restarted.

Link: https://lkml.kernel.org/r/20230724183157.3939892-15-Liam.Howlett@oracle.com
Signed-off-by: Liam R. Howlett 
Cc: Peng Zhang 
Cc: Suren Baghdasaryan 
Signed-off-by: Andrew Morton