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
