include/linux/maple_tree.h | 3 + kernel/fork.c | 34 ++- lib/maple_tree.c | 277 ++++++++++++++++++++++++- lib/test_maple_tree.c | 69 +++--- mm/mmap.c | 14 +- tools/testing/radix-tree/maple.c | 346 +++++++++++++++++++++++++++++++ 6 files changed, 697 insertions(+), 46 deletions(-)
In the process of duplicating mmap in fork(), VMAs will be inserted into the new
maple tree one by one. When inserting into the maple tree, the maple tree will
be rebalanced multiple times. The rebalancing of maple tree is not as fast as
the rebalancing of red-black tree and will be slower. Therefore, __mt_dup() is
introduced to directly duplicate the structure of the old maple tree, and then
modify each element of the new maple tree. This avoids rebalancing and some extra
copying, so is faster than the original method.
More information can refer to [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 numbers. There are 21 VMAs by default. The first row indicates
the number of added VMAs. The following two lines are the number of fork() calls
every 10 seconds. These numbers are different from the test results in v1 because
this time the benchmark is bound to a CPU. This way the numbers are more stable.
Increment of VMAs: 0 100 200 400 800 1600 3200 6400
6.5.0-next-20230829: 111878 75531 53683 35282 20741 11317 6110 3158
Apply this patchset: 114531 85420 64541 44592 28660 16371 9038 4831
+2.37% +13.09% +20.23% +26.39% +38.18% +44.66% +47.92% +52.98%
Todo:
- Update the documentation.
Changes since v1:
- Reimplement __mt_dup() and mtree_dup(). Loops are implemented without using
goto instructions.
- The new tree also needs to be locked to avoid some lockdep warnings.
- Drop and add some helpers.
- Add test for duplicating full tree.
- Drop mas_replace_entry(), it doesn't seem to have a big impact on the
performance of fork().
[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/
Peng Zhang (6):
maple_tree: Add two helpers
maple_tree: Introduce interfaces __mt_dup() and mtree_dup()
maple_tree: Add test for mtree_dup()
maple_tree: Skip other tests when BENCH is enabled
maple_tree: Update check_forking() and bench_forking()
fork: Use __mt_dup() to duplicate maple tree in dup_mmap()
include/linux/maple_tree.h | 3 +
kernel/fork.c | 34 ++-
lib/maple_tree.c | 277 ++++++++++++++++++++++++-
lib/test_maple_tree.c | 69 +++---
mm/mmap.c | 14 +-
tools/testing/radix-tree/maple.c | 346 +++++++++++++++++++++++++++++++
6 files changed, 697 insertions(+), 46 deletions(-)
--
2.20.1
See the attachment for the slightly modified benchmark./*******************************************************************************
* The BYTE UNIX Benchmarks - Release 3
* Module: spawn.c SID: 3.3 5/15/91 19:30:20
*
*******************************************************************************
* Bug reports, patches, comments, suggestions should be sent to:
*
* Ben Smith, Rick Grehan or Tom Yagerat BYTE Magazine
* ben@bytepb.byte.com rick_g@bytepb.byte.com tyager@bytepb.byte.com
*
*******************************************************************************
* Modification Log:
* $Header: spawn.c,v 3.4 87/06/22 14:32:48 kjmcdonell Beta $
* August 29, 1990 - Modified timing routines (ty)
* October 22, 1997 - code cleanup to remove ANSI C compiler warnings
* Andy Kahn <kahn@zk3.dec.com>
*
******************************************************************************/
char SCCSid[] = "@(#) @(#)spawn.c:3.3 -- 5/15/91 19:30:20";
/*
* Process creation
*
*/
#include <stdio.h>
#include <stdlib.h>
#include <signal.h>
#include <unistd.h>
#include <sys/wait.h>
#include <sys/mman.h>
volatile int stop;
unsigned long iter;
void wake_me(int seconds, void (*func)())
{
/* set up the signal handler */
signal(SIGALRM, func);
/* get the clock running */
alarm(seconds);
}
void report()
{
fprintf(stderr,"COUNT: %lu\n", iter);
iter = 0;
stop = 1;
}
void spawn()
{
int status, slave;
while (!stop) {
if ((slave = fork()) == 0) {
/* slave .. boring */
exit(0);
} else if (slave < 0) {
/* woops ... */
fprintf(stderr,"Fork failed at iteration %lu\n", iter);
perror("Reason");
exit(2);
} else
/* master */
wait(&status);
if (status != 0) {
fprintf(stderr,"Bad wait status: 0x%x\n", status);
exit(2);
}
iter++;
}
}
int main(int argc, char *argv[])
{
int duration, nr_vmas = 0;
size_t size;
void *addr;
if (argc != 2) {
fprintf(stderr,"Usage: %s duration \n", argv[0]);
exit(1);
}
duration = atoi(argv[1]);
size = 10 * getpagesize();
for (int i = 0; i <= 7000; ++i) {
if (i == nr_vmas) {
stop = 0;
fprintf(stderr,"VMAs: %d\n", i);
wake_me(duration, report);
spawn();
if (nr_vmas == 0)
nr_vmas = 100;
else nr_vmas *= 2;
}
addr = mmap(NULL, size, i & 1 ? PROT_READ : PROT_WRITE,
MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
if (addr == MAP_FAILED) {
perror("mmap");
exit(2);
}
}
}
* Peng Zhang <zhangpeng.00@bytedance.com> [230830 08:57]: > In the process of duplicating mmap in fork(), VMAs will be inserted into the new > maple tree one by one. When inserting into the maple tree, the maple tree will > be rebalanced multiple times. The rebalancing of maple tree is not as fast as > the rebalancing of red-black tree and will be slower. Therefore, __mt_dup() is > introduced to directly duplicate the structure of the old maple tree, and then > modify each element of the new maple tree. This avoids rebalancing and some extra > copying, so is faster than the original method. > More information can refer to [1]. Thanks for this patch set, it's really coming along nicely. > > 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 numbers. There are 21 VMAs by default. The first row indicates > the number of added VMAs. The following two lines are the number of fork() calls > every 10 seconds. These numbers are different from the test results in v1 because > this time the benchmark is bound to a CPU. This way the numbers are more stable. > > Increment of VMAs: 0 100 200 400 800 1600 3200 6400 > 6.5.0-next-20230829: 111878 75531 53683 35282 20741 11317 6110 3158 > Apply this patchset: 114531 85420 64541 44592 28660 16371 9038 4831 > +2.37% +13.09% +20.23% +26.39% +38.18% +44.66% +47.92% +52.98% Can you run this with the default 21 as well? > > Todo: > - Update the documentation. > > Changes since v1: > - Reimplement __mt_dup() and mtree_dup(). Loops are implemented without using > goto instructions. > - The new tree also needs to be locked to avoid some lockdep warnings. > - Drop and add some helpers. I guess this also includes the changes to remove the new ways of finding a node end and using that extra bit in the address? Those were significant and welcome changes. Thanks. > - Add test for duplicating full tree. > - Drop mas_replace_entry(), it doesn't seem to have a big impact on the > performance of fork(). > > [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/ > > Peng Zhang (6): > maple_tree: Add two helpers > maple_tree: Introduce interfaces __mt_dup() and mtree_dup() > maple_tree: Add test for mtree_dup() > maple_tree: Skip other tests when BENCH is enabled > maple_tree: Update check_forking() and bench_forking() > fork: Use __mt_dup() to duplicate maple tree in dup_mmap() > > include/linux/maple_tree.h | 3 + > kernel/fork.c | 34 ++- > lib/maple_tree.c | 277 ++++++++++++++++++++++++- > lib/test_maple_tree.c | 69 +++--- > mm/mmap.c | 14 +- > tools/testing/radix-tree/maple.c | 346 +++++++++++++++++++++++++++++++ > 6 files changed, 697 insertions(+), 46 deletions(-) > > -- > 2.20.1 >
© 2016 - 2025 Red Hat, Inc.