From: Peng Zhang <zhangpeng.00@bytedance.com>
To: "Liam R. Howlett" <Liam.Howlett@Oracle.com>
Cc: Peng Zhang <zhangpeng.00@bytedance.com>,
Danilo Krummrich <dakr@redhat.com>,
maple-tree@lists.infradead.org, linux-kernel@vger.kernel.org
Subject: Re: Maple Tree Work
Date: Wed, 12 Jul 2023 19:49:36 +0800 [thread overview]
Message-ID: <463899aa-6cbd-f08e-0aca-077b0e4e4475@bytedance.com> (raw)
In-Reply-To: <20230707163815.ns4kdz7iut5octjv@revolver>
在 2023/7/8 00:38, Liam R. Howlett 写道:
> - Fork & Dup tree + Delete DONT_COPY
> This is to optimize dup_mmap() in kernel/fork.c, but other
> users may want faster duplications of a tree.
> This should be faster than building a tree in bulk mode. The
> idea is to just copy each node and replace the pointers in,
> probably, a BFS order. Once the leaves are reached, the VMAs
> will be replaced by the copies made in fork, unless DONT_COPY is
> set, in which case the VMA will be deleted from the copied tree.
> DONT_COPY is not common and since the tree isn't visible, all
> nodes should be available for reuse (no RCU worries).
If DONT_COPY is set, this method will be complicated, because the gaps
adjacent to it need to be merged, and the gaps of all ancestor nodes
need to be updated.
I have another idea to build a tree, if inserted in order, we only
insert at the leaf node. All leaf nodes are connected using a linked
list. In the end we get a linked list with only leaf nodes. Then we
construct non-leaf nodes layer by layer from bottom to top. I think
this is also faster than bulk mode. Another advantage of this method
is that we are applicable to more scenarios, do not need the original
tree, only need to know the ranges inserted in order. I don't know
how fast this method is, so we can discuss it.
next prev parent reply other threads:[~2023-07-12 11:52 UTC|newest]
Thread overview: 10+ messages / expand[flat|nested] mbox.gz Atom feed top
2023-07-07 16:38 Maple Tree Work Liam R. Howlett
2023-07-12 11:49 ` Peng Zhang [this message]
2023-07-12 15:27 ` Liam R. Howlett
2023-07-13 8:05 ` Peng Zhang
2023-07-13 15:36 ` Liam R. Howlett
2023-07-14 12:32 ` Peng Zhang
2023-07-13 9:58 ` Peng Zhang
2023-07-13 15:52 ` Liam R. Howlett
2023-07-14 12:57 ` Matthew Wilcox
2023-07-14 13:32 ` Peng Zhang
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=463899aa-6cbd-f08e-0aca-077b0e4e4475@bytedance.com \
--to=zhangpeng.00@bytedance.com \
--cc=Liam.Howlett@Oracle.com \
--cc=dakr@redhat.com \
--cc=linux-kernel@vger.kernel.org \
--cc=maple-tree@lists.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;
as well as URLs for NNTP newsgroup(s).