Re: [PATCH 06/11] maple_tree: Introduce mas_replace_entry() to directly replace an entry
From: Peng Zhang
Date: Wed Aug 16 2023 - 09:12:36 EST
在 2023/8/1 00:48, Liam R. Howlett 写道:
* Peng Zhang <zhangpeng.00@xxxxxxxxxxxxx> [230731 08:39]:
在 2023/7/27 00:08, Liam R. Howlett 写道:
* Peng Zhang <zhangpeng.00@xxxxxxxxxxxxx> [230726 04:10]:
If mas has located a specific entry, it may be need to replace this
entry, so introduce mas_replace_entry() to do this. mas_replace_entry()
will be more efficient than mas_store*() because it doesn't do many
unnecessary checks.
This function should be inline, but more functions need to be moved to
the header file, so I didn't do it for the time being.
I am really nervous having no checks here. I get that this could be
used for duplicating the tree more efficiently, but having a function
that just swaps a value in is very dangerous - especially since it is
decoupled from the tree duplication code.
I've thought about this, and I feel like this is something the user
should be guaranteed. If the user is not sure whether to use it,
mas_store() can be used instead.
Documentation often isn't up to date and even more rarely read.
mas_replace_entry() does not give a hint of a requirement for a specific
state to the mas. This is not acceptable.
The description of the function also doesn't say anything about a
requirement of the maple state, just that it replaces an already
existing entry. You have to read the notes to find out that 'mas must
already locate an existing entry'.
And we should provide this interface
because it has better performance.
How much better is the performance? There's always a trade off but
without numbers, this is hard to justify.
I have implemented a new version of this pachset, and I will post it
soon.
I tested the benefits of mas_replace_entry() in userspace.
The test code is attached at the end.
Run three times:
mas_replace_entry(): 2.7613050s 2.7120030s 2.7274200s
mas_store(): 3.8451260s 3.8113200s 3.9334160s
Using mas_store() reduces the performance of duplicating VMAs by about
41%.
So I think mas_replace_entry() is necessary. We can describe it in more
detail in the documentation to prevent users from misusing it.
static noinline void __init bench_forking(struct maple_tree *mt)
{
struct maple_tree newmt;
int i, nr_entries = 134, nr_fork = 80000, ret;
void *val;
MA_STATE(mas, mt, 0, 0);
MA_STATE(newmas, &newmt, 0, 0);
clock_t start;
clock_t end;
double cpu_time_used = 0;
for (i = 0; i <= nr_entries; i++)
mtree_store_range(mt, i*10, i*10 + 5,
xa_mk_value(i), GFP_KERNEL);
for (i = 0; i < nr_fork; i++) {
mt_set_non_kernel(99999);
start = clock();
mt_init_flags(&newmt, MT_FLAGS_ALLOC_RANGE);
mas_lock(&newmas);
mas_lock(&mas);
ret = __mt_dup(mt, &newmt, GFP_NOWAIT | __GFP_NOWARN);
if (ret) {
pr_err("OOM!");
BUG_ON(1);
}
mas_set(&newmas, 0);
mas_for_each(&newmas, val, ULONG_MAX) {
mas_replace_entry(&newmas, val);
}
mas_unlock(&mas);
mas_unlock(&newmas);
end = clock();
cpu_time_used += ((double) (end - start));
mas_destroy(&newmas);
mt_validate(&newmt);
mt_set_non_kernel(0);
mtree_destroy(&newmt);
}
printf("time consumption:%.7fs\n", cpu_time_used / CLOCKS_PER_SEC);
}
Signed-off-by: Peng Zhang <zhangpeng.00@xxxxxxxxxxxxx>
---
include/linux/maple_tree.h | 1 +
lib/maple_tree.c | 25 +++++++++++++++++++++++++
2 files changed, 26 insertions(+)
diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h
index 229fe78e4c89..a05e9827d761 100644
--- a/include/linux/maple_tree.h
+++ b/include/linux/maple_tree.h
@@ -462,6 +462,7 @@ struct ma_wr_state {
void *mas_walk(struct ma_state *mas);
void *mas_store(struct ma_state *mas, void *entry);
+void mas_replace_entry(struct ma_state *mas, void *entry);
void *mas_erase(struct ma_state *mas);
int mas_store_gfp(struct ma_state *mas, void *entry, gfp_t gfp);
void mas_store_prealloc(struct ma_state *mas, void *entry);
diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index efac6761ae37..d58572666a00 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -5600,6 +5600,31 @@ void *mas_store(struct ma_state *mas, void *entry)
}
EXPORT_SYMBOL_GPL(mas_store);
+/**
+ * mas_replace_entry() - Replace an entry that already exists in the maple tree
+ * @mas: The maple state
+ * @entry: The entry to store
+ *
+ * Please note that mas must already locate an existing entry, and the new entry
+ * must not be NULL. If these two points cannot be guaranteed, please use
+ * mas_store*() instead, otherwise it will cause an internal error in the maple
+ * tree. This function does not need to allocate memory, so it must succeed.
+ */
+void mas_replace_entry(struct ma_state *mas, void *entry)
+{
+ void __rcu **slots;
+
+#ifdef CONFIG_DEBUG_MAPLE_TREE
+ MAS_WARN_ON(mas, !mte_is_leaf(mas->node));
+ MAS_WARN_ON(mas, !entry);
+ MAS_WARN_ON(mas, mas->offset >= mt_slots[mte_node_type(mas->node)]);
+#endif
+
+ slots = ma_slots(mte_to_node(mas->node), mte_node_type(mas->node));
+ rcu_assign_pointer(slots[mas->offset], entry);
+}
+EXPORT_SYMBOL_GPL(mas_replace_entry);
+
/**
* mas_store_gfp() - Store a value into the tree.
* @mas: The maple state
--
2.20.1