Message ID | 20231016032226.59199-1-zhangpeng.00@bytedance.com (mailing list archive) |
---|---|
Headers | show |
Series | Introduce __mt_dup() to improve the performance of fork() | expand |
在 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(-) >