Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20;
Message-ID: <463899aa-6cbd-f08e-0aca-077b0e4e4475@bytedance.com>
Date:   Wed, 12 Jul 2023 19:49:36 +0800
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:102.0)
 Gecko/20100101 Thunderbird/102.13.0
Subject: Re: Maple Tree Work
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
References: <20230707163815.ns4kdz7iut5octjv@revolver>
From:   Peng Zhang <zhangpeng.00@bytedance.com>
In-Reply-To: <20230707163815.ns4kdz7iut5octjv@revolver>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Precedence: bulk


在 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.