[PATCH v3 0/9] Introduce __mt_dup() to improve the performance of fork()

[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. 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