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. By applying __mt_dup() to dup_mmap(), better performance is achieved compared to the original method. After using this method, the average time complexity decreases from O(n * log(n)) to O(n). 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]. 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. By default, there are 21 VMAs. The first row shows the number of additional VMAs added on top of the default. The last two rows show the number of fork() calls per ten seconds. 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. Increment of VMAs: 0 100 200 400 800 1600 3200 6400 next-20230921: 112326 75469 54529 34619 20750 11355 6115 3183 Apply this: 116505 85971 67121 46080 29722 16665 9050 4805 +3.72% +13.92% +23.09% +33.11% +43.24% +46.76% +48.00% +50.96% Thanks to kernel test robot <oliver.sang@xxxxxxxxx> for reporting the warning about nested locks. Thanks to Liam for all the suggestions. Changes since v2: - Some minor modifications to mtree_dup(), __mt_dup() and their test code. - Introduce {mtree, mas}_lock_nested() to address lockdep warnings. - Update the documentation for maple tree. - Introduce undo_dup_mmap() to address the failure of dup_mmap(). - Performance data was retested based on the latest next-20230921, and there were some fluctuations in the results which were expected. [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/ Peng Zhang (9): 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() 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 | 1 + kernel/fork.c | 34 ++- lib/maple_tree.c | 300 ++++++++++++++++++++- lib/test_maple_tree.c | 69 +++-- mm/internal.h | 3 +- mm/memory.c | 7 +- mm/mmap.c | 52 +++- tools/include/linux/spinlock.h | 1 + tools/testing/radix-tree/maple.c | 363 ++++++++++++++++++++++++++ 11 files changed, 787 insertions(+), 54 deletions(-) -- 2.20.1