linux-kernel - Re: Maple Tree Work

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <463899aa-6cbd-f08e-0aca-077b0e4e4475@bytedance.com>
Date:   Wed, 12 Jul 2023 19:49:36 +0800
From:   Peng Zhang <zhangpeng.00@...edance.com>
To:     "Liam R. Howlett" <Liam.Howlett@...cle.com>
Cc:     Peng Zhang <zhangpeng.00@...edance.com>,
        Danilo Krummrich <dakr@...hat.com>,
        maple-tree@...ts.infradead.org, linux-kernel@...r.kernel.org
Subject: Re: Maple Tree Work

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