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

[Liam R. Howlett]

* Peng Zhang <zhangpeng.00@xxxxxxxxxxxxx> [231026 23:39]:
> 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.
> 
> This idea was originally from Liam R. Howlett's Maple Tree Work email, and I
> added some of my own ideas to implement it. Some previous discussions can be
> found in [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 to Liam and Matthew for the review.
> 
> Changes since v6:
>  - Add Liam's 'Reviewed-by' tag to all patches except for patch [3/10].
>  - Modify the copyright statement according to Matthew's opinion.
> 
> [1] https://lore.kernel.org/lkml/463899aa-6cbd-f08e-0aca-077b0e4e4475@xxxxxxxxxxxxx/
> [2] https://github.com/kdlucas/byte-unixbench/tree/master
> 
> v1: https://lore.kernel.org/lkml/20230726080916.17454-1-zhangpeng.00@xxxxxxxxxxxxx/
> v2: https://lore.kernel.org/lkml/20230830125654.21257-1-zhangpeng.00@xxxxxxxxxxxxx/
> v3: https://lore.kernel.org/lkml/20230925035617.84767-1-zhangpeng.00@xxxxxxxxxxxxx/
> v4: https://lore.kernel.org/lkml/20231009090320.64565-1-zhangpeng.00@xxxxxxxxxxxxx/
> v5: https://lore.kernel.org/lkml/20231016032226.59199-1-zhangpeng.00@xxxxxxxxxxxxx/
> v6: https://lore.kernel.org/lkml/20231024083258.65750-1-zhangpeng.00@xxxxxxxxxxxxx/
> 

Thanks, this looks good!

Reviewed-by: Liam R. Howlett <Liam.Howlett@xxxxxxxxxx>

> 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 +
>  include/linux/mm.h                    |  11 +
>  kernel/fork.c                         |  40 ++-
>  lib/maple_tree.c                      | 288 +++++++++++++++++++-
>  lib/test_maple_tree.c                 | 123 +++++----
>  mm/internal.h                         |  11 -
>  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 ++++++++++++++++++++++++++
>  13 files changed, 811 insertions(+), 102 deletions(-)
> 
> -- 
> 2.20.1
>