From: "Liam R. Howlett" <Liam.Howlett@oracle.com>
To: Andrew Morton <akpm@linux-foundation.org>
Cc: maple-tree@lists.infradead.org, linux-mm@kvack.org,
linux-kernel@vger.kernel.org,
"Paul E . McKenney" <paulmck@kernel.org>,
Suren Baghdasaryan <surenb@google.com>,
Matthew Wilcox <willy@infradead.org>,
"Liam R. Howlett" <Liam.Howlett@oracle.com>
Subject: [PATCH 3/6] maple_tree: introduce mas_put_in_tree()
Date: Fri, 4 Aug 2023 12:59:48 -0400 [thread overview]
Message-ID: <20230804165951.2661157-4-Liam.Howlett@oracle.com> (raw)
In-Reply-To: <20230804165951.2661157-1-Liam.Howlett@oracle.com>
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().
Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>
---
lib/maple_tree.c | 73 ++++++++++++++++++------------------------------
1 file changed, 27 insertions(+), 46 deletions(-)
diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 0d4573a8d134..c01b1be1480c 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -1715,45 +1715,32 @@ static inline void mas_adopt_children(struct ma_state *mas,
}
/*
- * mas_replace() - Replace a maple node in the tree with mas->node. Uses the
- * parent encoding to locate the maple node in the tree.
- * @mas - the ma_state to use for operations.
- * @advanced - boolean to adopt the child nodes and free the old node (false) or
- * leave the node (true) and handle the adoption and free elsewhere.
+ * mas_put_in_tree() - Put a new node in the tree, smp_wmb(), and mark the old
+ * node as dead.
+ * @mas - the maple state with the new node
+ * @old_enode - The old maple encoded node to replace.
*/
-static inline void mas_replace(struct ma_state *mas, bool advanced)
+static inline void mas_put_in_tree(struct ma_state *mas,
+ struct maple_enode *old_enode)
__must_hold(mas->tree->ma_lock)
{
- struct maple_node *mn = mas_mn(mas);
- struct maple_enode *old_enode;
- unsigned char offset = 0;
- void __rcu **slots = NULL;
-
- if (ma_is_root(mn)) {
- old_enode = mas_root_locked(mas);
- } else {
- offset = mte_parent_slot(mas->node);
- slots = ma_slots(mte_parent(mas->node),
- mas_parent_type(mas, mas->node));
- old_enode = mas_slot_locked(mas, slots, offset);
- }
-
- if (!advanced && !mte_is_leaf(mas->node))
- mas_adopt_children(mas, mas->node);
+ unsigned char offset;
+ void __rcu **slots;
if (mte_is_root(mas->node)) {
- mn->parent = ma_parent_ptr(
+ mas_mn(mas)->parent = ma_parent_ptr(
((unsigned long)mas->tree | MA_ROOT_PARENT));
rcu_assign_pointer(mas->tree->ma_root, mte_mk_root(mas->node));
mas_set_height(mas);
} else {
+
+ offset = mte_parent_slot(mas->node);
+ slots = ma_slots(mte_parent(mas->node),
+ mas_parent_type(mas, mas->node));
rcu_assign_pointer(slots[offset], mas->node);
}
- if (!advanced) {
- mte_set_node_dead(old_enode);
- mas_free(mas, old_enode);
- }
+ mte_set_node_dead(old_enode);
}
/*
@@ -1767,22 +1754,7 @@ static inline void mas_replace_node(struct ma_state *mas,
struct maple_enode *old_enode)
__must_hold(mas->tree->ma_lock)
{
- if (mte_is_root(mas->node)) {
- mas_mn(mas)->parent = ma_parent_ptr(
- ((unsigned long)mas->tree | MA_ROOT_PARENT));
- rcu_assign_pointer(mas->tree->ma_root, mte_mk_root(mas->node));
- mas_set_height(mas);
- } else {
- unsigned char offset = 0;
- void __rcu **slots = NULL;
-
- offset = mte_parent_slot(mas->node);
- slots = ma_slots(mte_parent(mas->node),
- mas_parent_type(mas, mas->node));
- rcu_assign_pointer(slots[offset], mas->node);
- }
-
- mte_set_node_dead(old_enode);
+ mas_put_in_tree(mas, old_enode);
mas_free(mas, old_enode);
}
@@ -2789,11 +2761,20 @@ static inline void mas_wmb_replace(struct ma_state *mas,
struct ma_topiary *free,
struct ma_topiary *destroy)
{
- /* All nodes must see old data as dead prior to replacing that data */
- smp_wmb(); /* Needed for RCU */
+ struct maple_enode *old_enode;
+
+ if (mte_is_root(mas->node)) {
+ old_enode = mas_root_locked(mas);
+ } else {
+ unsigned char offset = mte_parent_slot(mas->node);
+ void __rcu **slots = ma_slots(mte_parent(mas->node),
+ mas_parent_type(mas, mas->node));
+
+ old_enode = mas_slot_locked(mas, slots, offset);
+ }
/* Insert the new data in the tree */
- mas_replace(mas, true);
+ mas_put_in_tree(mas, old_enode);
if (!mte_is_leaf(mas->node))
mas_descend_adopt(mas);
--
2.39.2
next prev parent reply other threads:[~2023-08-04 17:00 UTC|newest]
Thread overview: 7+ messages / expand[flat|nested] mbox.gz Atom feed top
2023-08-04 16:59 [PATCH 0/6] maple_tree: Change replacement strategy Liam R. Howlett
2023-08-04 16:59 ` [PATCH 1/6] maple_tree: Add hex output to maple_arange64 dump Liam R. Howlett
2023-08-04 16:59 ` [PATCH 2/6] maple_tree: Reorder replacement of nodes to avoid live lock Liam R. Howlett
2023-08-04 16:59 ` Liam R. Howlett [this message]
2023-08-04 16:59 ` [PATCH 4/6] maple_tree: Introduce mas_tree_parent() definition Liam R. Howlett
2023-08-04 16:59 ` [PATCH 5/6] maple_tree: Change mas_adopt_children() parent usage Liam R. Howlett
2023-08-04 16:59 ` [PATCH 6/6] maple_tree: Replace data before marking dead in split and spanning store Liam R. Howlett
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20230804165951.2661157-4-Liam.Howlett@oracle.com \
--to=liam.howlett@oracle.com \
--cc=akpm@linux-foundation.org \
--cc=linux-kernel@vger.kernel.org \
--cc=linux-mm@kvack.org \
--cc=maple-tree@lists.infradead.org \
--cc=paulmck@kernel.org \
--cc=surenb@google.com \
--cc=willy@infradead.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox