Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::3:5 as permitted sender) client-ip=2620:137:e000::3:5;
Date:   Fri, 27 Oct 2023 10:27:20 -0400
From:   "Liam R. Howlett" <Liam.Howlett@Oracle.com>
To:     Peng Zhang <zhangpeng.00@bytedance.com>
Cc:     corbet@lwn.net, akpm@linux-foundation.org, willy@infradead.org,
        brauner@kernel.org, surenb@google.com, michael.christie@oracle.com,
        mjguzik@gmail.com, mathieu.desnoyers@efficios.com,
        npiggin@gmail.com, peterz@infradead.org, oliver.sang@intel.com,
        mst@redhat.com, maple-tree@lists.infradead.org, linux-mm@kvack.org,
        linux-doc@vger.kernel.org, linux-kernel@vger.kernel.org,
        linux-fsdevel@vger.kernel.org
Subject: Re: [PATCH v7 00/10] Introduce __mt_dup() to improve the performance
 of fork()
Message-ID: <20231027142720.vng5tny7xikiklen@revolver>
Mail-Followup-To: "Liam R. Howlett" <Liam.Howlett@Oracle.com>,
        Peng Zhang <zhangpeng.00@bytedance.com>, corbet@lwn.net,
        akpm@linux-foundation.org, willy@infradead.org, brauner@kernel.org,
        surenb@google.com, michael.christie@oracle.com, mjguzik@gmail.com,
        mathieu.desnoyers@efficios.com, npiggin@gmail.com,
        peterz@infradead.org, oliver.sang@intel.com, mst@redhat.com,
        maple-tree@lists.infradead.org, linux-mm@kvack.org,
        linux-doc@vger.kernel.org, linux-kernel@vger.kernel.org,
        linux-fsdevel@vger.kernel.org
References: <20231027033845.90608-1-zhangpeng.00@bytedance.com>
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <20231027033845.90608-1-zhangpeng.00@bytedance.com>
User-Agent: NeoMutt/20220429
MIME-Version: 1.0
X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-MessageData-0: =?us-ascii?Q?2IaRtMic08cLYH2JXt5liqA9XZmdlIUmhOvTdkvV15Nw2hs0iB+O3jfpA331?=
 =?us-ascii?Q?b+bSfMNAma26QeNIKtRXMsxgQXs8rdie8LlN9b2wsGgzjX7MYgNA6b28sjxg?=
 =?us-ascii?Q?pZYTRTFRBaOJxu9+68BfCfrEyY6j+UF855wPZGU7nnRtiD2ywLQ1S6jSzdJp?=
 =?us-ascii?Q?0O3ZhZ+DGv0dfFFARc4gKzVD3c5frvLg8ig3v6tvOHGXYTA9gT6Y39nB3Zcr?=
 =?us-ascii?Q?hek95aGY1liH/JCGvqoTpZcTqIAq7iBc6Y8k5IxwbxE702thH++Ai2vlfDtB?=
 =?us-ascii?Q?2bBoYcrP6oDL6DT9KnAcd+rgtuQtHnBs7qIRAmHpM2qGbessIgP35rsCPOrK?=
 =?us-ascii?Q?pDP9b6Ir36EcqIXCOXAMx3ffVQ2V44UV5uJbCaEyzhY0ZdZ9Bojz2DJzW8VQ?=
 =?us-ascii?Q?sQnwHqIn5//ZbXcx2Ynpk+OnUcbauigHFb8oXYabyg9yya9Lx3mnZMsdd5va?=
 =?us-ascii?Q?TkVRyEN5kkdb04iFcd3I51yXoc1oAbdphgaQEVWjEt338WoZvPSxByuR9grR?=
 =?us-ascii?Q?rHftVsghJPupjysoEOugTGD49BS7r0MuG6WckeNWOKrrou5MNGclZIA86vw0?=
 =?us-ascii?Q?EjkFzrFnPBP5WTpKX22ASAkavB/G6AsNp4pTrQ+jQ+EoEDSPvRqb1BdQ0z6f?=
 =?us-ascii?Q?F0+3NXjE5T7dTOmEovz6+AsmvajCiCqRmFMjvdLjk9g1O9iIsDSEc8C8LxIl?=
 =?us-ascii?Q?rvCaCrtOJdTak6vZgd+rKT9vv4hQGVGXDwxTyh0jAgWZFwWILCcrRuLKgkm6?=
 =?us-ascii?Q?Tos4+vaHqCVT9CaB9i/ynbS5jtgljcgC/N61debrxQ+Cdl2mxMQ9N8SuRCYQ?=
 =?us-ascii?Q?crAax+16isOZYBktFfKDJ8bouGAvmLwSj77eUEY5r2pYZrw2eElVv+tYyvl0?=
 =?us-ascii?Q?t6bEttUeLvfsQsVBy3qdeBTXUcHSzY+mRD+7+rVPxxWiGZNcC3rKEK2KsoZ3?=
 =?us-ascii?Q?vqTh5bAju/akW9nGEwV7gtgVUhlkO68bLZgJ9xHTGYd++xhbidFg9gd5d6KJ?=
 =?us-ascii?Q?TkP445WSEHnVoNDUZ75i69cqA5e5/0pBmySSMFm2PjQf5FmfvPxqC+4FWSnW?=
 =?us-ascii?Q?Mr01V5oGZc9mAFf5dMpVudwfBQx7I3bNgpyTedMJWJcA5mcv0jRpf3YpDND2?=
 =?us-ascii?Q?NgQfOTUms4vaZTnpGRgYBHT6rWeSpRC5nLOJS5lOY8GZS3W/5IKbLkFUgBlB?=
 =?us-ascii?Q?0ClP5Psx/D7mS509zZdlWdPtWoDqf8M05VcXZeOlWmwh0i8aQyglNM1OgJA3?=
 =?us-ascii?Q?v+k80tipEkVKdFjB1xz9/Akkjsjb6mNNtS+epiD1Ov3kQQzsWXE3S1Ip+vYk?=
 =?us-ascii?Q?ZOpiSyzZO1nD4ZKzmoePCf9Pcu/MvdRjWyusHw1jKE2NvFTBjvGepE5zlgon?=
 =?us-ascii?Q?9L+0CBS4x+52EbW8GZkyH0Eqh9sCZXA4S4frUsUjMoH6MA5ZDedrTaYDl2js?=
 =?us-ascii?Q?dMzObiHVgjbp3XU3aFAnPNSk1X7LiylBhtDhN7XmJgacIIdHFKLVkKmduff2?=
 =?us-ascii?Q?Lz/gny57cl+4YLZoedHv7mUrZ7QA/Hc1Q1ovZLi42R4grsp6lqJdjOev6qXG?=
 =?us-ascii?Q?cVjGmgZUnc5Ucxpe/jJt0jF1ghQzHkv+hZcwNQ7r?=
X-MS-Exchange-AntiSpam-ExternalHop-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-ExternalHop-MessageData-0: =?us-ascii?Q?77f1V5ZJME9o47mcrn5iEPRD5SZ/jWFahI4SuqcznyRYUHLkqDuA5V2RbTPq?=
 =?us-ascii?Q?vSF7Fx3iygk8Nq3HLQn7qfQVfRjundMzLa7qWyb2SYZpYYzfUCFceFvy4/qX?=
 =?us-ascii?Q?ODQD36HeC7fWP21bpjePPjjxanFPTJwxZYQwdDF8kiksPUlOVY49EFYNeny/?=
 =?us-ascii?Q?V1IEcWLrh9FZQ8mSmkve+qFVfRP2BV2mQme+ndFXfyB2HjZoyK0b0clDjUZx?=
 =?us-ascii?Q?yFTLVfb9w39ZR9UTHOJ1okIGtgJziJD0gBZTMWdz/16uME3zgsqCBCPkMr3P?=
 =?us-ascii?Q?h2/E22kjHXCH9N6AxFunSXklo8y7YT+WOilNBi58BlKtj23cMTR+Xly7atJg?=
 =?us-ascii?Q?LhFxFsMBsfnLFuIj8Nmd6s3XxnOeY6BnSuOUJklirn79rxnAD/uKCwDZgxLZ?=
 =?us-ascii?Q?ukPPlErIHjnFUNYQFrBrQ16bkQy9TmZzEMVNcAQckfQK7P4p0utbwWLqWqp4?=
 =?us-ascii?Q?QmZT7SkHjioxRrKlwY9Mt95YDHiwRZhvIhd6W0B6EzARyzgpwqupqdSID+na?=
 =?us-ascii?Q?bqclD6JrnNTcWoTypSkRktZb2mb4SrBN2plb+MxeO03JXERNn9oUGfK+KRn+?=
 =?us-ascii?Q?/OvRWDUf9r1wloCr/Hvy9u2RjcJ4ALMIGE+N5gNlAME8WMGzEgeuphnqW6hP?=
 =?us-ascii?Q?fEAWN4yjPrfsMDdrM0b62ZjP1klPjiQ/wa5IAZOTAJnlp6VlnZrb4R1sNKo9?=
 =?us-ascii?Q?0decsRvdozFL8qOs2SXYbZU88ehxmk6H3SIYjVRJguYUlBOmDzaXfiJAFwbA?=
 =?us-ascii?Q?Shz0XcG4rSndJ7K6UC+yTzn84ks3FxtD93i7wCYXqExVhyC9J+7oWWgC2Bvj?=
 =?us-ascii?Q?xE5rYexTW9/R5hlTgrb+EbJ8cyLh1468Vx/6nqNfBd9tH046hC4jJBPipmwg?=
 =?us-ascii?Q?b3LDIcXdswRqOpV8KXaByAz+O56WZpdcehZ0bsNUU8GrdX0MRsOyWjDkB66d?=
 =?us-ascii?Q?wFT1TTu6Gq2r2WA1nM9d7sBLx3PpW4FMPSFZZ2VfGQx+qcIWR9wkc6Gubzq1?=
 =?us-ascii?Q?cVsTuH1VljQk+5/ETzBv/uRJuIXfAoESPeDGRpMUuB2Fnd/i7wpqVtyGBkDF?=
 =?us-ascii?Q?W7NkyT2Ch+79YHWjjyEKc8DHNngUupvSeIREWb17vKNDi8+yFOueS8NnEXop?=
 =?us-ascii?Q?M03U9ugrLBQhH8TORySMJQ+eAR8HVmexzF6ShQuQdVCamENJg5PHY6Y=3D?=
X-OriginatorOrg: oracle.com
X-MS-Exchange-CrossTenant-Network-Message-Id: b9a662e3-a8d3-4967-c142-08dbd6f8d60e
X-MS-Exchange-CrossTenant-AuthSource: SN6PR10MB3022.namprd10.prod.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 27 Oct 2023 14:27:23.5689
 (UTC)
X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted
X-MS-Exchange-CrossTenant-Id: 4e2c6054-71cb-48f1-bd6c-3a9705aca71b
X-MS-Exchange-CrossTenant-MailboxType: HOSTED
X-MS-Exchange-CrossTenant-UserPrincipalName: 3SQAqGnWIBVUIJMBA6Nl715t9ZXDwR1yM3I5gAOPvcqnxvpKY7TS7odVMr7lzNi4zmsTpIaGeGmkCMwyESQY3g==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: DM6PR10MB4299
X-Proofpoint-Virus-Version: vendor=baseguard
 engine=ICAP:2.0.272,Aquarius:18.0.987,Hydra:6.0.619,FMLib:17.11.176.26
 definitions=2023-10-27_12,2023-10-27_01,2023-05-22_02
X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 suspectscore=0 mlxscore=0 adultscore=0
 phishscore=0 spamscore=0 mlxlogscore=999 bulkscore=0 malwarescore=0
 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2310240000
 definitions=main-2310270125
X-Proofpoint-ORIG-GUID: T8ds3Bu1vx1POn1hcI8i8Y572PutkBVt
X-Proofpoint-GUID: T8ds3Bu1vx1POn1hcI8i8Y572PutkBVt
X-Spam-Status: No, score=-0.8 required=5.0 tests=DKIM_SIGNED,DKIM_VALID,
	DKIM_VALID_AU,HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI,
	SPF_HELO_NONE,SPF_PASS autolearn=unavailable autolearn_force=no
	version=3.4.6
X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on groat.vger.email
Precedence: bulk
List-ID: <linux-kernel.vger.kernel.org>
X-Mailing-List: linux-kernel@vger.kernel.org
X-Greylist: Sender passed SPF test, not delayed by milter-greylist-4.6.4 (groat.vger.email [0.0.0.0]); Fri, 27 Oct 2023 07:28:52 -0700 (PDT)

* Peng Zhang <zhangpeng.00@bytedance.com> [231026 23:39]:
> 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.
> 
> This idea was originally from Liam R. Howlett's Maple Tree Work email, and I
> added some of my own ideas to implement it. Some previous discussions can be
> found in [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 to Liam and Matthew for the review.
> 
> Changes since v6:
>  - Add Liam's 'Reviewed-by' tag to all patches except for patch [3/10].
>  - Modify the copyright statement according to Matthew's opinion.
> 
> [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/
> v5: https://lore.kernel.org/lkml/20231016032226.59199-1-zhangpeng.00@bytedance.com/
> v6: https://lore.kernel.org/lkml/20231024083258.65750-1-zhangpeng.00@bytedance.com/
> 

Thanks, this looks good!

Reviewed-by: Liam R. Howlett <Liam.Howlett@oracle.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 +
>  include/linux/mm.h                    |  11 +
>  kernel/fork.c                         |  40 ++-
>  lib/maple_tree.c                      | 288 +++++++++++++++++++-
>  lib/test_maple_tree.c                 | 123 +++++----
>  mm/internal.h                         |  11 -
>  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 ++++++++++++++++++++++++++
>  13 files changed, 811 insertions(+), 102 deletions(-)
> 
> -- 
> 2.20.1
>