Steven Rostedt and Andrew Morton
fd003fac7c
maple_tree: document that "last" in mtree_insert_range() is inclusive
...
The kernel doc of mtree_insert_range() does not state if the address
represented by the "last" parameter is inclusive or exclusive. This can
lead to bugs by code that assumes it is exclusive. Explicitly state that
the parameter is inclusive.
Link: https://lore.kernel.org/20260512175623.4c5ca8d2@gandalf.local.home
Signed-off-by: Steven Rostedt <rostedt@goodmis.org >
Reviewed-by: "Liam R. Howlett" <liam@infradead.org >
Acked-by: SeongJae Park <sj@kernel.org >
Cc: Alice Ryhl <aliceryhl@google.com >
Cc: Andrew Ballance <andrewjballance@gmail.com >
Cc: Matthew Wilcox (Oracle) <willy@infradead.org >
Signed-off-by: Andrew Morton <akpm@linux-foundation.org >
2026-06-02 15:22:14 -07:00
Liam R. Howlett and Andrew Morton
77a50e9652
MAINTAINERS: update Liam's email address
...
Switching to private email address. Update all contact information
Add an entry to mailmap at the same time.
Link: https://lore.kernel.org/20260422184310.2682901-1-liam@infradead.org
Signed-off-by: Liam R. Howlett <liam@infradead.org >
Signed-off-by: Andrew Morton <akpm@linux-foundation.org >
2026-04-27 05:54:25 -07:00
Liam R. Howlett and Andrew Morton
0e8cf9a31a
maple_tree: clean up mas_wr_node_store()
...
The new_end does not need to be passed in as the data is already being
checked. This allows for other areas to skip getting the node new_end in
the calling function.
The type was incorrectly void * instead of void __rcu *, which isn't an
issue but is technically incorrect.
Move the variable assignment to after the declarations to clean up the
initial setup.
Ensure there is something to copy before calling memcpy().
Link: https://lkml.kernel.org/r/20260130205935.2559335-31-Liam.Howlett@oracle.com
Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com >
Cc: Alice Ryhl <aliceryhl@google.com >
Cc: Andrew Ballance <andrewjballance@gmail.com >
Cc: Arnd Bergmann <arnd@arndb.de >
Cc: Christian Kujau <lists@nerdbynature.de >
Cc: Geert Uytterhoeven <geert@linux-m68k.org >
Cc: Kuninori Morimoto <kuninori.morimoto.gx@renesas.com >
Cc: Matthew Wilcox (Oracle) <willy@infradead.org >
Cc: SeongJae Park <sj@kernel.org >
Cc: Sidhartha Kumar <sidhartha.kumar@oracle.com >
Cc: Suren Baghdasaryan <surenb@google.com >
Cc: Vlastimil Babka <vbabka@suse.cz >
Signed-off-by: Andrew Morton <akpm@linux-foundation.org >
2026-04-05 13:52:57 -07:00
Liam R. Howlett and Andrew Morton
b82f4c811e
maple_tree: don't pass end to mas_wr_append()
...
Figure out the end internally. This is necessary for future cleanups.
Link: https://lkml.kernel.org/r/20260130205935.2559335-30-Liam.Howlett@oracle.com
Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com >
Cc: Alice Ryhl <aliceryhl@google.com >
Cc: Andrew Ballance <andrewjballance@gmail.com >
Cc: Arnd Bergmann <arnd@arndb.de >
Cc: Christian Kujau <lists@nerdbynature.de >
Cc: Geert Uytterhoeven <geert@linux-m68k.org >
Cc: Kuninori Morimoto <kuninori.morimoto.gx@renesas.com >
Cc: Matthew Wilcox (Oracle) <willy@infradead.org >
Cc: SeongJae Park <sj@kernel.org >
Cc: Sidhartha Kumar <sidhartha.kumar@oracle.com >
Cc: Suren Baghdasaryan <surenb@google.com >
Cc: Vlastimil Babka <vbabka@suse.cz >
Signed-off-by: Andrew Morton <akpm@linux-foundation.org >
2026-04-05 13:52:57 -07:00
Liam R. Howlett and Andrew Morton
2969241fa2
maple_tree: pass maple copy node to mas_wmb_replace()
...
mas_wmb_replace() is called in three places with the same setup, move the
setup into the function itself. The function needs to be relocated as it
calls mtree_range_walk().
Link: https://lkml.kernel.org/r/20260130205935.2559335-29-Liam.Howlett@oracle.com
Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com >
Cc: Alice Ryhl <aliceryhl@google.com >
Cc: Andrew Ballance <andrewjballance@gmail.com >
Cc: Arnd Bergmann <arnd@arndb.de >
Cc: Christian Kujau <lists@nerdbynature.de >
Cc: Geert Uytterhoeven <geert@linux-m68k.org >
Cc: Kuninori Morimoto <kuninori.morimoto.gx@renesas.com >
Cc: Matthew Wilcox (Oracle) <willy@infradead.org >
Cc: SeongJae Park <sj@kernel.org >
Cc: Sidhartha Kumar <sidhartha.kumar@oracle.com >
Cc: Suren Baghdasaryan <surenb@google.com >
Cc: Vlastimil Babka <vbabka@suse.cz >
Signed-off-by: Andrew Morton <akpm@linux-foundation.org >
2026-04-05 13:52:57 -07:00
Liam R. Howlett and Andrew Morton
b8852ef30c
maple_tree: remove maple big node and subtree structs
...
Now that no one uses the structures and functions, drop the dead code.
Link: https://lkml.kernel.org/r/20260130205935.2559335-28-Liam.Howlett@oracle.com
Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com >
Cc: Alice Ryhl <aliceryhl@google.com >
Cc: Andrew Ballance <andrewjballance@gmail.com >
Cc: Arnd Bergmann <arnd@arndb.de >
Cc: Christian Kujau <lists@nerdbynature.de >
Cc: Geert Uytterhoeven <geert@linux-m68k.org >
Cc: Kuninori Morimoto <kuninori.morimoto.gx@renesas.com >
Cc: Matthew Wilcox (Oracle) <willy@infradead.org >
Cc: SeongJae Park <sj@kernel.org >
Cc: Sidhartha Kumar <sidhartha.kumar@oracle.com >
Cc: Suren Baghdasaryan <surenb@google.com >
Cc: Vlastimil Babka <vbabka@suse.cz >
Signed-off-by: Andrew Morton <akpm@linux-foundation.org >
2026-04-05 13:52:57 -07:00
Liam R. Howlett and Andrew Morton
280b792cac
maple_tree: use maple copy node for mas_wr_split()
...
Instead of using the maple big node, use the maple copy node for reduced
stack usage and aligning with mas_wr_rebalance() and
mas_wr_spanning_store().
Splitting a node is similar to rebalancing, but a new evaluation of when
to ascend is needed. The only other difference is that the data is pushed
and never rebalanced at each level.
The testing must also align with the changes to this commit to ensure the
test suite continues to pass.
Link: https://lkml.kernel.org/r/20260130205935.2559335-27-Liam.Howlett@oracle.com
Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com >
Cc: Alice Ryhl <aliceryhl@google.com >
Cc: Andrew Ballance <andrewjballance@gmail.com >
Cc: Arnd Bergmann <arnd@arndb.de >
Cc: Christian Kujau <lists@nerdbynature.de >
Cc: Geert Uytterhoeven <geert@linux-m68k.org >
Cc: Kuninori Morimoto <kuninori.morimoto.gx@renesas.com >
Cc: Matthew Wilcox (Oracle) <willy@infradead.org >
Cc: SeongJae Park <sj@kernel.org >
Cc: Sidhartha Kumar <sidhartha.kumar@oracle.com >
Cc: Suren Baghdasaryan <surenb@google.com >
Cc: Vlastimil Babka <vbabka@suse.cz >
Signed-off-by: Andrew Morton <akpm@linux-foundation.org >
2026-04-05 13:52:56 -07:00
Liam R. Howlett and Andrew Morton
11e7f22f5e
maple_tree: add cp_converged() helper
...
When the maple copy node converges into a single entry, then certain
operations can stop ascending the tree.
This is used more later.
Link: https://lkml.kernel.org/r/20260130205935.2559335-26-Liam.Howlett@oracle.com
Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com >
Cc: Alice Ryhl <aliceryhl@google.com >
Cc: Andrew Ballance <andrewjballance@gmail.com >
Cc: Arnd Bergmann <arnd@arndb.de >
Cc: Christian Kujau <lists@nerdbynature.de >
Cc: Geert Uytterhoeven <geert@linux-m68k.org >
Cc: Kuninori Morimoto <kuninori.morimoto.gx@renesas.com >
Cc: Matthew Wilcox (Oracle) <willy@infradead.org >
Cc: SeongJae Park <sj@kernel.org >
Cc: Sidhartha Kumar <sidhartha.kumar@oracle.com >
Cc: Suren Baghdasaryan <surenb@google.com >
Cc: Vlastimil Babka <vbabka@suse.cz >
Signed-off-by: Andrew Morton <akpm@linux-foundation.org >
2026-04-05 13:52:56 -07:00
Liam R. Howlett and Andrew Morton
0abff20819
maple_tree: add copy_tree_location() helper
...
Extract the copying of the tree location from one maple state to another
into its own function. This is used more later.
Link: https://lkml.kernel.org/r/20260130205935.2559335-25-Liam.Howlett@oracle.com
Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com >
Cc: Alice Ryhl <aliceryhl@google.com >
Cc: Andrew Ballance <andrewjballance@gmail.com >
Cc: Arnd Bergmann <arnd@arndb.de >
Cc: Christian Kujau <lists@nerdbynature.de >
Cc: Geert Uytterhoeven <geert@linux-m68k.org >
Cc: Kuninori Morimoto <kuninori.morimoto.gx@renesas.com >
Cc: Matthew Wilcox (Oracle) <willy@infradead.org >
Cc: SeongJae Park <sj@kernel.org >
Cc: Sidhartha Kumar <sidhartha.kumar@oracle.com >
Cc: Suren Baghdasaryan <surenb@google.com >
Cc: Vlastimil Babka <vbabka@suse.cz >
Signed-off-by: Andrew Morton <akpm@linux-foundation.org >
2026-04-05 13:52:56 -07:00
Liam R. Howlett and Andrew Morton
971f0db159
maple_tree: use maple copy node for mas_wr_rebalance() operation
...
Stop using the maple big node for rebalance operations by changing to more
align with spanning store. The rebalance operation needs its own data
calculation in rebalance_data().
In the event of too much data, the rebalance tries to push the data using
push_data_sib(). If there is insufficient data, the rebalance operation
will rebalance against a sibling (found with rebalance_sib()).
The rebalance starts at the leaf and works its way upward in the tree
using rebalance_ascend(). Most of the code is shared with spanning store
such as the copy node having a new root, but is fundamentally different in
that the data must come from a sibling.
A parent maple state is used to track the parent location to avoid
multiple mas_ascend() calls. The maple state tree location is copied from
the parent to the mas (child) in the ascend step. Ascending itself is
done in the main loop.
Link: https://lkml.kernel.org/r/20260130205935.2559335-23-Liam.Howlett@oracle.com
Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com >
Cc: Alice Ryhl <aliceryhl@google.com >
Cc: Andrew Ballance <andrewjballance@gmail.com >
Cc: Arnd Bergmann <arnd@arndb.de >
Cc: Christian Kujau <lists@nerdbynature.de >
Cc: Geert Uytterhoeven <geert@linux-m68k.org >
Cc: Kuninori Morimoto <kuninori.morimoto.gx@renesas.com >
Cc: Matthew Wilcox (Oracle) <willy@infradead.org >
Cc: SeongJae Park <sj@kernel.org >
Cc: Sidhartha Kumar <sidhartha.kumar@oracle.com >
Cc: Suren Baghdasaryan <surenb@google.com >
Cc: Vlastimil Babka <vbabka@suse.cz >
Signed-off-by: Andrew Morton <akpm@linux-foundation.org >
2026-04-05 13:52:56 -07:00
Liam R. Howlett and Andrew Morton
b00a1804e6
maple_tree: add cp_is_new_root() helper
...
Add a helper to do what is needed when the maple copy node contains a new
root node. This is useful for future commits and is self-documenting
code.
[Liam.Howlett@oracle.com: remove warnings on older compilers]
Link: https://lkml.kernel.org/r/malwmirqnpuxqkqrobcmzfkmmxipoyzwfs2nwc5fbpxlt2r2ej@wchmjtaljvw3
[akpm@linux-foundation.org: s/cp->slot[0]/&cp->slot[0]/, per Liam]
Link: https://lkml.kernel.org/r/20260130205935.2559335-22-Liam.Howlett@oracle.com
Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com >
Cc: Alice Ryhl <aliceryhl@google.com >
Cc: Andrew Ballance <andrewjballance@gmail.com >
Cc: Arnd Bergmann <arnd@arndb.de >
Cc: Christian Kujau <lists@nerdbynature.de >
Cc: Geert Uytterhoeven <geert@linux-m68k.org >
Cc: Kuninori Morimoto <kuninori.morimoto.gx@renesas.com >
Cc: Matthew Wilcox (Oracle) <willy@infradead.org >
Cc: SeongJae Park <sj@kernel.org >
Cc: Sidhartha Kumar <sidhartha.kumar@oracle.com >
Cc: Suren Baghdasaryan <surenb@google.com >
Cc: Vlastimil Babka <vbabka@suse.cz >
Signed-off-by: Andrew Morton <akpm@linux-foundation.org >
2026-04-05 13:52:56 -07:00
Liam R. Howlett and Andrew Morton
62e9d349af
maple_tree: separate wr_split_store and wr_rebalance store type code path
...
The split and rebalance store types both go through the same function that
uses the big node. Separate the code paths so that each can be updated
independently.
No functional change intended
Link: https://lkml.kernel.org/r/20260130205935.2559335-21-Liam.Howlett@oracle.com
Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com >
Cc: Alice Ryhl <aliceryhl@google.com >
Cc: Andrew Ballance <andrewjballance@gmail.com >
Cc: Arnd Bergmann <arnd@arndb.de >
Cc: Christian Kujau <lists@nerdbynature.de >
Cc: Geert Uytterhoeven <geert@linux-m68k.org >
Cc: Kuninori Morimoto <kuninori.morimoto.gx@renesas.com >
Cc: Matthew Wilcox (Oracle) <willy@infradead.org >
Cc: SeongJae Park <sj@kernel.org >
Cc: Sidhartha Kumar <sidhartha.kumar@oracle.com >
Cc: Suren Baghdasaryan <surenb@google.com >
Cc: Vlastimil Babka <vbabka@suse.cz >
Signed-off-by: Andrew Morton <akpm@linux-foundation.org >
2026-04-05 13:52:56 -07:00
Liam R. Howlett and Andrew Morton
448ec8c0a4
maple_tree: remove unnecessary return statements
...
Functions do not need to state return at the end, unless skipping unwind.
These can safely be dropped.
Link: https://lkml.kernel.org/r/20260130205935.2559335-20-Liam.Howlett@oracle.com
Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com >
Cc: Alice Ryhl <aliceryhl@google.com >
Cc: Andrew Ballance <andrewjballance@gmail.com >
Cc: Arnd Bergmann <arnd@arndb.de >
Cc: Christian Kujau <lists@nerdbynature.de >
Cc: Geert Uytterhoeven <geert@linux-m68k.org >
Cc: Kuninori Morimoto <kuninori.morimoto.gx@renesas.com >
Cc: Matthew Wilcox (Oracle) <willy@infradead.org >
Cc: SeongJae Park <sj@kernel.org >
Cc: Sidhartha Kumar <sidhartha.kumar@oracle.com >
Cc: Suren Baghdasaryan <surenb@google.com >
Cc: Vlastimil Babka <vbabka@suse.cz >
Signed-off-by: Andrew Morton <akpm@linux-foundation.org >
2026-04-05 13:52:55 -07:00
Liam R. Howlett and Andrew Morton
3578d61c1c
maple_tree: inline mas_wr_spanning_rebalance()
...
Now that the spanning rebalance is small, fully inline it in
mas_wr_spanning_store().
No functional change.
Link: https://lkml.kernel.org/r/20260130205935.2559335-19-Liam.Howlett@oracle.com
Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com >
Cc: Alice Ryhl <aliceryhl@google.com >
Cc: Andrew Ballance <andrewjballance@gmail.com >
Cc: Arnd Bergmann <arnd@arndb.de >
Cc: Christian Kujau <lists@nerdbynature.de >
Cc: Geert Uytterhoeven <geert@linux-m68k.org >
Cc: Kuninori Morimoto <kuninori.morimoto.gx@renesas.com >
Cc: Matthew Wilcox (Oracle) <willy@infradead.org >
Cc: SeongJae Park <sj@kernel.org >
Cc: Sidhartha Kumar <sidhartha.kumar@oracle.com >
Cc: Suren Baghdasaryan <surenb@google.com >
Cc: Vlastimil Babka <vbabka@suse.cz >
Signed-off-by: Andrew Morton <akpm@linux-foundation.org >
2026-04-05 13:52:55 -07:00
Liam R. Howlett and Andrew Morton
a9c6716e08
maple_tree: start using maple copy node for destination
...
Stop using the maple subtree state and big node in favour of using three
destinations in the maple copy node. That is, expand the way leaves were
handled to all levels of the tree and use the maple copy node to track the
new nodes.
Extract out the sibling init into the data calculation since this is where
the insufficient data can be detected. The remainder of the sibling code
to shift the next iteration is moved to the spanning_ascend() function,
since it is not always needed.
Next introduce the dst_setup() function which will decide how many nodes
are needed to contain the data at this level. Using the destination
count, populate the copy node's dst array with the new nodes and set
d_count to the correct value. Note that this can be tricky in the case of
a leaf node with exactly enough room because of the rule against NULLs at
the end of leaves.
Once the destinations are ready, copy the data by altering the
cp_data_write() function to copy from the sources to the destinations
directly. This eliminates the use of the big node in this code path. On
node completion, node_finalise() will zero out the remaining area and set
the metadata, if necessary.
spanning_ascend() is used to decide if the operation is complete. It may
create a new root, converge into one destination, or continue upwards by
ascending the left and right write maple states.
One test case setup needed to be tweaked so that the targeted node was
surrounded by full nodes.
[akpm@linux-foundation.org: coding-style cleanups]
Link: https://lkml.kernel.org/r/20260130205935.2559335-18-Liam.Howlett@oracle.com
Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com >
Cc: Alice Ryhl <aliceryhl@google.com >
Cc: Andrew Ballance <andrewjballance@gmail.com >
Cc: Arnd Bergmann <arnd@arndb.de >
Cc: Christian Kujau <lists@nerdbynature.de >
Cc: Geert Uytterhoeven <geert@linux-m68k.org >
Cc: Kuninori Morimoto <kuninori.morimoto.gx@renesas.com >
Cc: Matthew Wilcox (Oracle) <willy@infradead.org >
Cc: SeongJae Park <sj@kernel.org >
Cc: Sidhartha Kumar <sidhartha.kumar@oracle.com >
Cc: Suren Baghdasaryan <surenb@google.com >
Cc: Vlastimil Babka <vbabka@suse.cz >
Signed-off-by: Andrew Morton <akpm@linux-foundation.org >
2026-04-05 13:52:55 -07:00
Liam R. Howlett and Andrew Morton
20b20162e1
maple_tree: add gap support, slot and pivot sizes for maple copy
...
Add plumbing work for using maple copy as a normal node for a source of
copy operations. This is needed later.
Link: https://lkml.kernel.org/r/20260130205935.2559335-17-Liam.Howlett@oracle.com
Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com >
Cc: Alice Ryhl <aliceryhl@google.com >
Cc: Andrew Ballance <andrewjballance@gmail.com >
Cc: Arnd Bergmann <arnd@arndb.de >
Cc: Christian Kujau <lists@nerdbynature.de >
Cc: Geert Uytterhoeven <geert@linux-m68k.org >
Cc: Kuninori Morimoto <kuninori.morimoto.gx@renesas.com >
Cc: Matthew Wilcox (Oracle) <willy@infradead.org >
Cc: SeongJae Park <sj@kernel.org >
Cc: Sidhartha Kumar <sidhartha.kumar@oracle.com >
Cc: Suren Baghdasaryan <surenb@google.com >
Cc: Vlastimil Babka <vbabka@suse.cz >
Signed-off-by: Andrew Morton <akpm@linux-foundation.org >
2026-04-05 13:52:55 -07:00
Liam R. Howlett and Andrew Morton
de7f3ed37c
maple_tree: introduce ma_leaf_max_gap()
...
This is the same as mas_leaf_max_gap(), but the information necessary is
known without a maple state in future code. Adding this function now
simplifies the review for a subsequent patch.
Link: https://lkml.kernel.org/r/20260130205935.2559335-16-Liam.Howlett@oracle.com
Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com >
Cc: Alice Ryhl <aliceryhl@google.com >
Cc: Andrew Ballance <andrewjballance@gmail.com >
Cc: Arnd Bergmann <arnd@arndb.de >
Cc: Christian Kujau <lists@nerdbynature.de >
Cc: Geert Uytterhoeven <geert@linux-m68k.org >
Cc: Kuninori Morimoto <kuninori.morimoto.gx@renesas.com >
Cc: Matthew Wilcox (Oracle) <willy@infradead.org >
Cc: SeongJae Park <sj@kernel.org >
Cc: Sidhartha Kumar <sidhartha.kumar@oracle.com >
Cc: Suren Baghdasaryan <surenb@google.com >
Cc: Vlastimil Babka <vbabka@suse.cz >
Signed-off-by: Andrew Morton <akpm@linux-foundation.org >
2026-04-05 13:52:55 -07:00
Liam R. Howlett and Andrew Morton
6953038cab
maple_tree: change initial big node setup in mas_wr_spanning_rebalance()
...
Instead of copying the data into the big node and finding out that the
data may need to be moved or appended to, calculate the data space up
front (in the maple copy node) and set up another source for the copy.
The additional copy source is tracked in the maple state sib (short for
sibling), and is put into the maple write states for future operations
after the data is in the big node.
To facilitate the newly moved node, some initial setup of the maple
subtree state are relocated after the potential shift caused by the new
way of rebalancing against a sibling.
Link: https://lkml.kernel.org/r/20260130205935.2559335-15-Liam.Howlett@oracle.com
Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com >
Cc: Alice Ryhl <aliceryhl@google.com >
Cc: Andrew Ballance <andrewjballance@gmail.com >
Cc: Arnd Bergmann <arnd@arndb.de >
Cc: Christian Kujau <lists@nerdbynature.de >
Cc: Geert Uytterhoeven <geert@linux-m68k.org >
Cc: Kuninori Morimoto <kuninori.morimoto.gx@renesas.com >
Cc: Matthew Wilcox (Oracle) <willy@infradead.org >
Cc: SeongJae Park <sj@kernel.org >
Cc: Sidhartha Kumar <sidhartha.kumar@oracle.com >
Cc: Suren Baghdasaryan <surenb@google.com >
Cc: Vlastimil Babka <vbabka@suse.cz >
Signed-off-by: Andrew Morton <akpm@linux-foundation.org >
2026-04-05 13:52:55 -07:00
Liam R. Howlett and Andrew Morton
f141d56643
maple_tree: inline mas_spanning_rebalance_loop() into mas_wr_spanning_rebalance()
...
Just copy the code and replace count with height. This is done to avoid
affecting other code paths into mas_spanning_rebalance_loop() for the next
change.
No functional change intended.
Link: https://lkml.kernel.org/r/20260130205935.2559335-14-Liam.Howlett@oracle.com
Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com >
Cc: Alice Ryhl <aliceryhl@google.com >
Cc: Andrew Ballance <andrewjballance@gmail.com >
Cc: Arnd Bergmann <arnd@arndb.de >
Cc: Christian Kujau <lists@nerdbynature.de >
Cc: Geert Uytterhoeven <geert@linux-m68k.org >
Cc: Kuninori Morimoto <kuninori.morimoto.gx@renesas.com >
Cc: Matthew Wilcox (Oracle) <willy@infradead.org >
Cc: SeongJae Park <sj@kernel.org >
Cc: Sidhartha Kumar <sidhartha.kumar@oracle.com >
Cc: Suren Baghdasaryan <surenb@google.com >
Cc: Vlastimil Babka <vbabka@suse.cz >
Signed-off-by: Andrew Morton <akpm@linux-foundation.org >
2026-04-05 13:52:55 -07:00
Liam R. Howlett and Andrew Morton
9ec1e972c3
maple_tree: introduce maple_copy node and use it in mas_spanning_rebalance()
...
Introduce an internal-memory only node type called maple_copy to
facilitate internal copy operations. Use it in mas_spanning_rebalance()
for just the leaf nodes. Initially, the maple_copy node is used to
configure the source nodes and copy the data into the big_node.
The maple_copy contains a list of source entries with start and end
offsets. One of the maple_copy entries can be itself with an offset of 0
to 2, representing the data where the store partially overwrites entries,
or fully overwrites the entry. The side effect is that the source nodes
no longer have to worry about partially copying the existing offset if it
is not fully overwritten.
This is in preparation of removal of the maple big_node, but for the time
being the data is copied to the big node to limit the change size.
Link: https://lkml.kernel.org/r/20260130205935.2559335-12-Liam.Howlett@oracle.com
Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com >
Cc: Alice Ryhl <aliceryhl@google.com >
Cc: Andrew Ballance <andrewjballance@gmail.com >
Cc: Arnd Bergmann <arnd@arndb.de >
Cc: Christian Kujau <lists@nerdbynature.de >
Cc: Geert Uytterhoeven <geert@linux-m68k.org >
Cc: Kuninori Morimoto <kuninori.morimoto.gx@renesas.com >
Cc: Matthew Wilcox (Oracle) <willy@infradead.org >
Cc: SeongJae Park <sj@kernel.org >
Cc: Sidhartha Kumar <sidhartha.kumar@oracle.com >
Cc: Suren Baghdasaryan <surenb@google.com >
Cc: Vlastimil Babka <vbabka@suse.cz >
Signed-off-by: Andrew Morton <akpm@linux-foundation.org >
2026-04-05 13:52:54 -07:00
Liam R. Howlett and Andrew Morton
6b74d44b62
maple_tree: correct right ma_wr_state end pivot in mas_wr_spanning_store()
...
The end_piv will be needed in the next patch set and has not been set
correctly in this code path. Correct the oversight before using it.
Link: https://lkml.kernel.org/r/20260130205935.2559335-11-Liam.Howlett@oracle.com
Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com >
Cc: Alice Ryhl <aliceryhl@google.com >
Cc: Andrew Ballance <andrewjballance@gmail.com >
Cc: Arnd Bergmann <arnd@arndb.de >
Cc: Christian Kujau <lists@nerdbynature.de >
Cc: Geert Uytterhoeven <geert@linux-m68k.org >
Cc: Kuninori Morimoto <kuninori.morimoto.gx@renesas.com >
Cc: Matthew Wilcox (Oracle) <willy@infradead.org >
Cc: SeongJae Park <sj@kernel.org >
Cc: Sidhartha Kumar <sidhartha.kumar@oracle.com >
Cc: Suren Baghdasaryan <surenb@google.com >
Cc: Vlastimil Babka <vbabka@suse.cz >
Signed-off-by: Andrew Morton <akpm@linux-foundation.org >
2026-04-05 13:52:54 -07:00
Liam R. Howlett and Andrew Morton
2fce1c3c47
maple_tree: move maple_subtree_state from mas_wr_spanning_store to mas_wr_spanning_rebalance
...
Moving the maple_subtree_state is necessary for future cleanups and is
only set up in mas_wr_spanning_rebalance() but never used.
Link: https://lkml.kernel.org/r/20260130205935.2559335-10-Liam.Howlett@oracle.com
Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com >
Cc: Alice Ryhl <aliceryhl@google.com >
Cc: Andrew Ballance <andrewjballance@gmail.com >
Cc: Arnd Bergmann <arnd@arndb.de >
Cc: Christian Kujau <lists@nerdbynature.de >
Cc: Geert Uytterhoeven <geert@linux-m68k.org >
Cc: Kuninori Morimoto <kuninori.morimoto.gx@renesas.com >
Cc: Matthew Wilcox (Oracle) <willy@infradead.org >
Cc: SeongJae Park <sj@kernel.org >
Cc: Sidhartha Kumar <sidhartha.kumar@oracle.com >
Cc: Suren Baghdasaryan <surenb@google.com >
Cc: Vlastimil Babka <vbabka@suse.cz >
Signed-off-by: Andrew Morton <akpm@linux-foundation.org >
2026-04-05 13:52:54 -07:00
Liam R. Howlett and Andrew Morton
3680159527
maple_tree: don't pass through height in mas_wr_spanning_store
...
Height is not used locally in the function, so call the height argument
closer to where it is passed in the next level.
Link: https://lkml.kernel.org/r/20260130205935.2559335-9-Liam.Howlett@oracle.com
Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com >
Cc: Alice Ryhl <aliceryhl@google.com >
Cc: Andrew Ballance <andrewjballance@gmail.com >
Cc: Arnd Bergmann <arnd@arndb.de >
Cc: Christian Kujau <lists@nerdbynature.de >
Cc: Geert Uytterhoeven <geert@linux-m68k.org >
Cc: Kuninori Morimoto <kuninori.morimoto.gx@renesas.com >
Cc: Matthew Wilcox (Oracle) <willy@infradead.org >
Cc: SeongJae Park <sj@kernel.org >
Cc: Sidhartha Kumar <sidhartha.kumar@oracle.com >
Cc: Suren Baghdasaryan <surenb@google.com >
Cc: Vlastimil Babka <vbabka@suse.cz >
Signed-off-by: Andrew Morton <akpm@linux-foundation.org >
2026-04-05 13:52:54 -07:00
Liam R. Howlett and Andrew Morton
41bcc348f2
maple_tree: remove l_wr_mas from mas_wr_spanning_rebalance
...
Use the wr_mas instead of creating another variable on the stack. Take
the opportunity to remove l_mas from being used anywhere but in the
maple_subtree_state.
Link: https://lkml.kernel.org/r/20260130205935.2559335-8-Liam.Howlett@oracle.com
Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com >
Cc: Alice Ryhl <aliceryhl@google.com >
Cc: Andrew Ballance <andrewjballance@gmail.com >
Cc: Arnd Bergmann <arnd@arndb.de >
Cc: Christian Kujau <lists@nerdbynature.de >
Cc: Geert Uytterhoeven <geert@linux-m68k.org >
Cc: Kuninori Morimoto <kuninori.morimoto.gx@renesas.com >
Cc: Matthew Wilcox (Oracle) <willy@infradead.org >
Cc: SeongJae Park <sj@kernel.org >
Cc: Sidhartha Kumar <sidhartha.kumar@oracle.com >
Cc: Suren Baghdasaryan <surenb@google.com >
Cc: Vlastimil Babka <vbabka@suse.cz >
Signed-off-by: Andrew Morton <akpm@linux-foundation.org >
2026-04-05 13:52:54 -07:00
Liam R. Howlett and Andrew Morton
3dd3dbaac1
maple_tree: make ma_wr_states reliable for reuse in spanning store
...
mas_extend_spanning_null() was not modifying the range min and range max
of the resulting store operation. The result was that the maple write
state no longer matched what the write was doing. This was not an issue
as the values were previously not used, but to make the ma_wr_state usable
in future changes, the range min/max stored in the ma_wr_state for left
and right need to be consistent with the operation.
Link: https://lkml.kernel.org/r/20260130205935.2559335-7-Liam.Howlett@oracle.com
Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com >
Cc: Alice Ryhl <aliceryhl@google.com >
Cc: Andrew Ballance <andrewjballance@gmail.com >
Cc: Arnd Bergmann <arnd@arndb.de >
Cc: Christian Kujau <lists@nerdbynature.de >
Cc: Geert Uytterhoeven <geert@linux-m68k.org >
Cc: Kuninori Morimoto <kuninori.morimoto.gx@renesas.com >
Cc: Matthew Wilcox (Oracle) <willy@infradead.org >
Cc: SeongJae Park <sj@kernel.org >
Cc: Sidhartha Kumar <sidhartha.kumar@oracle.com >
Cc: Suren Baghdasaryan <surenb@google.com >
Cc: Vlastimil Babka <vbabka@suse.cz >
Signed-off-by: Andrew Morton <akpm@linux-foundation.org >
2026-04-05 13:52:54 -07:00
