Re: [PATCH 06/11] maple_tree: Introduce mas_replace_entry() to directly replace an entry
From: Peng Zhang
Date: Fri Aug 18 2023 - 05:41:16 EST
在 2023/8/17 01:40, Liam R. Howlett 写道:
* Peng Zhang <zhangpeng.00@xxxxxxxxxxxxx> [230816 09:11]:
在 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
This runtime is too short, we should increase the number of elements or
loops until it is over 10 seconds. This will make the setup time
and other variances less significant and we can use the command run time
as a rough estimate of performance. IIRC 134 was picked for a rough
estimate of an average task size so maybe increase the loops.
I changed nr_entries to 1000, and the measured numbers are as follows:
mas_replace_entry(): 20.0375820s
mas_store(): 28.6175720s
It can be seen that mas_store() is still nearly 40% slower.
I understand the numbers here are from clock recordings to demonstrate
the significance of your change.
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.
I think something is necessary for a quicker replacement, yes. I don't
want to go as far as you did with the lack of checking.
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
CONFIG_DEBUG_MAPLE_TREE is not necessary, MAS_WRAN_ON() will be compiled
out if it's not set.
+ 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