Re: [PATCH 06/11] maple_tree: Introduce mas_replace_entry() to directly replace an entry

["Liam R. Howlett" <Liam.Howlett@Oracle.com>]

* Peng Zhang <zhangpeng.00@bytedance.com> [230816 09:11]:
> 
> 
> 在 2023/8/1 00:48, Liam R. Howlett 写道:
> > * Peng Zhang <zhangpeng.00@bytedance.com> [230731 08:39]:
> > > 
> > > 
> > > 在 2023/7/27 00:08, Liam R. Howlett 写道:
> > > > * Peng Zhang <zhangpeng.00@bytedance.com> [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 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@bytedance.com>
> > > > > ---
> > > > >    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
> > > > >