[PATCH v5 00/10] Introduce __mt_dup() to improve the performance of fork()

[Peng Zhang]

在 2023/10/16 11:22, Peng Zhang 写道:
> Hi all,
> 
> This series introduces __mt_dup() to improve the performance of fork(). During
> the duplication process of mmap, all VMAs are traversed and inserted one by one
> into the new maple tree, causing the maple tree to be rebalanced multiple times.
> Balancing the maple tree is a costly operation. To duplicate VMAs more
> efficiently, mtree_dup() and __mt_dup() are introduced for the maple tree. They
> can efficiently duplicate a maple tree.
> 
> Here are some algorithmic details about {mtree,__mt}_dup(). We perform a DFS
> pre-order traversal of all nodes in the source maple tree. During this process,
> we fully copy the nodes from the source tree to the new tree. This involves
> memory allocation, and when encountering a new node, if it is a non-leaf node,
> all its child nodes are allocated at once.
> 
> Some previous discussions can be referred to as [1]. For a more detailed
> analysis of the algorithm, please refer to the logs for patch [3/10] and patch
> [10/10]
> 
> There is a "spawn" in byte-unixbench[2], which can be used to test the
> performance of fork(). I modified it slightly to make it work with
> different number of VMAs.
> 
> Below are the test results. The first row shows the number of VMAs.
> The second and third rows show the number of fork() calls per ten seconds,
> corresponding to next-20231006 and the this patchset, respectively. The
> test results were obtained with CPU binding to avoid scheduler load
> balancing that could cause unstable results. There are still some
> fluctuations in the test results, but at least they are better than the
> original performance.
> 
> 21     121   221    421    821    1621   3221   6421   12821  25621  51221
> 112100 76261 54227  34035  20195  11112  6017   3161   1606   802    393
> 114558 83067 65008  45824  28751  16072  8922   4747   2436   1233   599
> 2.19%  8.92% 19.88% 34.64% 42.37% 44.64% 48.28% 50.17% 51.68% 53.74% 52.42%
> 
> Thanks for Liam's review.
> 
> Changes since v4:
>   - Change the handling method for the failure of dup_mmap(). Handle it in
>     exit_mmap().
>   - Update check_forking() and bench_forking().
>   - Add the corresponding copyright statement.
> 
I apologize for forgetting to include all the links while editing the cover letter.
Here they are:
[1] https://lore.kernel.org/lkml/463899aa-6cbd-f08e-0aca-077b0e4e4475@bytedance.com/
[2] https://github.com/kdlucas/byte-unixbench/tree/master

v1: https://lore.kernel.org/lkml/20230726080916.17454-1-zhangpeng.00@bytedance.com/
v2: https://lore.kernel.org/lkml/20230830125654.21257-1-zhangpeng.00@bytedance.com/
v3: https://lore.kernel.org/lkml/20230925035617.84767-1-zhangpeng.00@bytedance.com/
v4: https://lore.kernel.org/lkml/20231009090320.64565-1-zhangpeng.00@bytedance.com/

> Peng Zhang (10):
>    maple_tree: Add mt_free_one() and mt_attr() helpers
>    maple_tree: Introduce {mtree,mas}_lock_nested()
>    maple_tree: Introduce interfaces __mt_dup() and mtree_dup()
>    radix tree test suite: Align kmem_cache_alloc_bulk() with kernel
>      behavior.
>    maple_tree: Add test for mtree_dup()
>    maple_tree: Update the documentation of maple tree
>    maple_tree: Skip other tests when BENCH is enabled
>    maple_tree: Update check_forking() and bench_forking()
>    maple_tree: Preserve the tree attributes when destroying maple tree
>    fork: Use __mt_dup() to duplicate maple tree in dup_mmap()
> 
>   Documentation/core-api/maple_tree.rst |   4 +
>   include/linux/maple_tree.h            |   7 +
>   kernel/fork.c                         |  39 ++-
>   lib/maple_tree.c                      | 304 ++++++++++++++++++++-
>   lib/test_maple_tree.c                 | 123 +++++----
>   mm/memory.c                           |   7 +-
>   mm/mmap.c                             |   9 +-
>   tools/include/linux/rwsem.h           |   4 +
>   tools/include/linux/spinlock.h        |   1 +
>   tools/testing/radix-tree/linux.c      |  45 +++-
>   tools/testing/radix-tree/maple.c      | 363 ++++++++++++++++++++++++++
>   11 files changed, 815 insertions(+), 91 deletions(-)
>