Re: Maple Tree Work

[Peng Zhang]

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