Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.34 as permitted sender) client-ip=23.128.96.34;
Date:   Thu, 26 Oct 2023 14:18:43 -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 v6 00/10] Introduce __mt_dup() to improve the performance
 of fork()
Message-ID: <20231026181843.amjq27uffssn2nf2@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: <20231024083258.65750-1-zhangpeng.00@bytedance.com>
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <20231024083258.65750-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?D1ggP/luzuM7CSV1d2o2jeWWi6OsBXtMqjyVKBrMHPz+oWiz0BLdrK3k0nnZ?=
 =?us-ascii?Q?D1B8Baa+IFbsNF3ges6/Xb7D7b6uxlWOvrs0x2Zu08NzbHlW9PMgt6evJcoU?=
 =?us-ascii?Q?IwBfWG0gqabahglIcmCWvSsRhQUpiwBJx/BThh/aeN53UoqPErT2Am9Twf5F?=
 =?us-ascii?Q?h0L43nCGm2lm8NeS6r2L3GYJK7Qg7pVSVLi3TZOSccPwfL73F7qbXK+woU9V?=
 =?us-ascii?Q?RLCJRpEbcIT7ysbbXupvqTwlPH0JfJSvbcw6OSJNWkX5OfOjVemNKznEYJ4x?=
 =?us-ascii?Q?h6He2eptY8pPYpy4Qju6vyQKsb5whVwmHdzDy0p2hNpR6bYKp4AdZ4Mz+nCw?=
 =?us-ascii?Q?wRmM7CFGqbFbRJxAb1EUBJ0Vte5QqWBeMGzMB+sTshiWNV9N8lq4yg7bb1Gi?=
 =?us-ascii?Q?iwaGsr6Uv2pvlbbOEJuTUq/LPO6uwUQOYWzuEnQ2ubAjzfmXtEUcELZMOA6U?=
 =?us-ascii?Q?tde3L5GaiEEphKD2Ft+WkkfH0+86U+ZcOHUlU1JZnO1+UytCCes2q5fUzuw+?=
 =?us-ascii?Q?6SjAoWrG8irkZifdjok/9k2XZJGCNxNmTcIQoeiTUAWslz7Xgbe/9OslibN6?=
 =?us-ascii?Q?R6u03G3NJREPA5LxzYiow9pSyr1WfaC1sbaGKT1SEhYcbccSL0p9za/KKQA6?=
 =?us-ascii?Q?i2te6rcSNWs3Tk98ooJbkSREDfoLyUZvv6c+QpNwq/Xbvj0uxbKEDls19YLA?=
 =?us-ascii?Q?uUs16pPnN/YSVmohNWF8AQUdgx1Z8X3FF1x7GnEKC0b3FjZnNgxdy5981Iyb?=
 =?us-ascii?Q?c8jfxy3P5+ay/zp7xdczY+MMsy9nIDo1OIQNEatba1IHfv1lbEL+Dh4Ywoc5?=
 =?us-ascii?Q?zzwHCcTSZX6I6tC57lEA7diW/awYse3Njev2L19nWO4ZG2Jk/TXzf0Q7vQ2q?=
 =?us-ascii?Q?B2pINsMBKTH9s2ofWHrTzWyuH2UpblZNqHIHmy/1uedt7DmRvwUc3cqS6Rsh?=
 =?us-ascii?Q?a1TyVwKEFA1Z13AQ8eZmSWNt/NRTZx1s/6IP01FNZA6YHV9EYAZmO7CvwgPh?=
 =?us-ascii?Q?CcdB1dQnZIoDbJaKmi4g/pdtVFxXg2UV5BPsIzjD6uKxoihdL8DFLrcKCYt/?=
 =?us-ascii?Q?HaJLCYYR3yQQwQtaWgIsYxnH3axYtGj2gdiJK+U9AtYh7Gsi4Vd6jJISD88V?=
 =?us-ascii?Q?sLITtnPnFIlaFRaKL/mMJ79Dglga+JcjQmAe5s6Mxo6Y0YJPA/Lein3nf3sX?=
 =?us-ascii?Q?NvCtj5HbhjEnnhcW0NjSOKFs4dUuCsvb37MikjNkc27Lm7Vm5X38isq0KS7z?=
 =?us-ascii?Q?QHK2YuIPoh1dWKvogwjRmGvwDmTGqNQUZG/a+gE/V+OGF2tpyHjCWtX5bN4m?=
 =?us-ascii?Q?NchG0LGZyg7K1DOKFPDlG9akR/idz9AjuYPWVMnHbqsC9YVuSD6R0MoAzm5b?=
 =?us-ascii?Q?pUXbnyvDPmch3WSP1TBAEo93XybSQBvY7J0v/DGUicwUG9ebzDqcj0nUaaxk?=
 =?us-ascii?Q?DP4xK2zVpjmn8GCncaO4A57333RMJ5J9zoUkXA1jEY/dQ5xZB+aCW9aWepkp?=
 =?us-ascii?Q?jQMBAfKN9S4tdFHeVNn8v8524mZLgVq2YJVAfZWZH97Ny+R2pKzI/ofU+rLH?=
 =?us-ascii?Q?I6qxqPCEZQu5HdGGQM0eZQ9kDqJ/VFOg+oaQeleb?=
X-MS-Exchange-AntiSpam-ExternalHop-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-ExternalHop-MessageData-0: =?us-ascii?Q?+Uzd7IrQNgaY5eR9imxRiJ4uSSFP9PUY3PK92oG+u7iyYpOfOfbDARIh5Ft0?=
 =?us-ascii?Q?WMppHBfL9w87Cwrmx/Eg28tpwDWQA/ou8B+qihC3fNhYssZlB7A/OuAzrn/B?=
 =?us-ascii?Q?zPWoueASOcWDRNK+kJpXIRcmrg0CUbJwNyESldUkJ8XDiVKi7KtoeB2e2viG?=
 =?us-ascii?Q?v75mttjusELOVii7kVp2TBnwAlpLgfwKo8M74+VjCgTF0D4Smv/e3Q+e8wwN?=
 =?us-ascii?Q?/QZswGZEOTyVOR3gEwtwbtIn5ImdNdsctdA7hE2tabWZ/D1Dzc+/ey+nKVhq?=
 =?us-ascii?Q?7RwGWRaEdQjrqK1EubmMFIe/1k4rlpRLwyUoccDRcgeBJW2cvoVVd7pCALUh?=
 =?us-ascii?Q?zLqnkT0lF5jqk3IZvruxbHbHVw9EOF+bU83OrUX2sBLBtM1BNj0iqBDDycq6?=
 =?us-ascii?Q?r9N61uTQCO9rCsY9IMPjzY+qjxs5/xyLFwZxQwvV5S68Ueps7tdiY5eZsy3d?=
 =?us-ascii?Q?R3cF+3JgtcJ1kufLFxHMPWvy/WObNN/AhnIj5/+iV4sG5OmIyduzAkRUZs2R?=
 =?us-ascii?Q?ac0KTObcv9vGlKVuWrekRu7k3+osrVEysFPwEZMjYOl8ECE9OSLcf14yV+4B?=
 =?us-ascii?Q?BQEe+7HVoKmr7LEjUdiv5yhpanjFCdmA5zBWZ0KOjCycWP20DhdAsjz5Rfl8?=
 =?us-ascii?Q?zqEr67zOEPI2h9+M2Xf0kPXQQOiV1mf1z8ZHyDrVBX59dPVLqdUUPVSbbXZR?=
 =?us-ascii?Q?8HI+6WMwsjD7hrti9D1QZoCnjIIQLA0099MB7/szaxWnAhHHVCvv3LWw9sfP?=
 =?us-ascii?Q?WMPmyBn9BusZtt5z+eo9h71IB6Hlyeh3IN8x7xvCHyozW7UgF5Vv+wSmpP2k?=
 =?us-ascii?Q?2Xy7g151CAgD6/Roe5D+t5M2ZX2cbGbAmwXRfHyIQZF2DBeTisaJlHbAiDob?=
 =?us-ascii?Q?Gv12tyn+sS8n+c1cguii/bRbM7V5zalwv9t8TFCxbQwnFM76P6DtDSbvV2jn?=
 =?us-ascii?Q?os+tpIycyFFjvQUHyhzpcQ2jvI6ctcYMYiO/L9xg7YC03W+g04GMlhZznOd4?=
 =?us-ascii?Q?LyWN2I0ST0sVXNJIz/m23R758+1NOgZmUFk3ejhLhlOn9n1M3qE+8wrzWzun?=
 =?us-ascii?Q?qirqg217gjochDGNi5GpbUvtqW1a1/p9g4R/H+Iq4kCECd+HD/pfsPvefZS5?=
 =?us-ascii?Q?fLoWZ07Febj7WR/M6bpTKKOkkyQIk9FlwNOayowBpFYhKMfJOU7ZrK0=3D?=
X-OriginatorOrg: oracle.com
X-MS-Exchange-CrossTenant-Network-Message-Id: c1ba20b3-0513-4259-ebd5-08dbd64ffe45
X-MS-Exchange-CrossTenant-AuthSource: SN6PR10MB3022.namprd10.prod.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 26 Oct 2023 18:18:46.2776
 (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: ORMNitHoYhYSJJu7OG42pTCGhvt+3fx3B+BpBwhWpaLimaGaqZu3HSmkGUuFxMyLrXGujRZwuXFsZCC1gIGLzw==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: CH0PR10MB4985
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-26_16,2023-10-26_01,2023-05-22_02
X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 bulkscore=0 adultscore=0 suspectscore=0
 phishscore=0 malwarescore=0 mlxscore=0 mlxlogscore=999 spamscore=0
 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2310170001
 definitions=main-2310260159
X-Proofpoint-GUID: QQEASqHONejCKdxy-Z75fu2bjpsM49Pf
X-Proofpoint-ORIG-GUID: QQEASqHONejCKdxy-Z75fu2bjpsM49Pf
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 howler.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 (howler.vger.email [0.0.0.0]); Thu, 26 Oct 2023 11:20:18 -0700 (PDT)

* Peng Zhang <zhangpeng.00@bytedance.com> [231024 04:33]:
> 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.

Besides the one comment by Matthew, this series looks good.

> 
> Changes since v5:
>  - Correct the copyright statement.
>  - Add Suggested-by tag in patch [3/10] and [10/10], this work was originally
>    proposed by Liam R. Howlett.
>  - Some cleanup and comment corrections for patch [3/10].
>  - Use vma_iter* series interfaces as much as possible in [10/10].
> 
> [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/
> 
> 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()
> 

Besides 03/10, please add:
Reviewed-by: Liam R. Howlett <Liam.Howlett@oracle.com>

Thanks for all the work on this,
Liam