Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20;
Date:   Fri, 2 Jun 2023 14:55:55 -0400
From:   "Liam R. Howlett" <Liam.Howlett@Oracle.com>
To:     "Yin, Fengwei" <fengwei.yin@intel.com>
Cc:     Andrew Morton <akpm@linux-foundation.org>,
        maple-tree@lists.infradead.org, linux-mm@kvack.org,
        linux-kernel@vger.kernel.org, "Liu, Yujie" <yujie.liu@intel.com>
Subject: Re: [PATCH 00/14] Reduce preallocations for maple tree
Message-ID: <20230602185555.irsxyt7svz7h6igm@revolver>
Mail-Followup-To: "Liam R. Howlett" <Liam.Howlett@Oracle.com>,
        "Yin, Fengwei" <fengwei.yin@intel.com>,
        Andrew Morton <akpm@linux-foundation.org>,
        maple-tree@lists.infradead.org, linux-mm@kvack.org,
        linux-kernel@vger.kernel.org, "Liu, Yujie" <yujie.liu@intel.com>
References: <20230601021605.2823123-1-Liam.Howlett@oracle.com>
 <7a5dc9ce-b58f-e1b3-db1a-d00a8a556ae5@intel.com>
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <7a5dc9ce-b58f-e1b3-db1a-d00a8a556ae5@intel.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?/LDu7X5TBSr6WgptL70WpqiP39uveJlZcz0x6t7ycG4Z2okrFiaSOSSxeODC?=
 =?us-ascii?Q?a5voRqU9VWImv18wsdKwBtHyFmLl4aNhoZurZNCXRM0l78MXs7fNQ/AA7cRe?=
 =?us-ascii?Q?DJhUuXyoJdaNTapoplGTSgDww5zweEj2b4aDu9ApJcHIXWfmhGDlEtZxMjaH?=
 =?us-ascii?Q?OGf/0378OpG3eggU9r3/CL01/dxsAG2ur2NNJN+1wwy6wTl0JPHjA+P6cul3?=
 =?us-ascii?Q?GiidczUBatnJNRfU3nS7Q4RAsnaceghdnrEbZBkt5S54vatTzvHifIOmMS30?=
 =?us-ascii?Q?9KBSVAKWN86f5i9J4U/03nBZLlhB9xgy8OXIWI4izJDT6tTHrM0Qu3NCAQni?=
 =?us-ascii?Q?IG2nWdk/mhhkbyzjwTjIpiP1ecWoPFv5pBDbMiigTe2wadhVImQltgSL4SXX?=
 =?us-ascii?Q?hZDhzLRgIPuaFWZKX6U1ebRahyR/YIwRiPUWiHO/8h9xz+CzQv1c+jyakocR?=
 =?us-ascii?Q?xY9DO+YfFQpfSyj49Pmm6rTbuRAvSFVr+PPUP2vys5uRYvCbyctdOOB0lvS2?=
 =?us-ascii?Q?lFiu4ieS+0hFwadyqp9wAlSzllLLQA5UA5p1c5dbGWQiaTe72ILMVnfhC/Gv?=
 =?us-ascii?Q?rEkhYNlCQNzTDITLB56eiRQYzfVuCumuhV+tODxRQucNi4976p19ogTFTyA7?=
 =?us-ascii?Q?RNv6gvWbMRIvg/q3FhEi9i/qSHHThabYP7oMj0ViF4qygvpLHqOquKyon5xI?=
 =?us-ascii?Q?ps0wFj5EI31dIXoK+aRxc95RpK5nrQobyqPF9eoRdf2svfNWJCT1z8vCxlla?=
 =?us-ascii?Q?efdgJATLv7dkcwssDsR5q3q/f6nR/55vmsWbaHU9XDjUViTuS+Xv9pNxLvhu?=
 =?us-ascii?Q?LNGvamXIWpBeTFexNUMAXMPMZNFN59f4wN/JByce1d62lWneY8PF5L9RYsXq?=
 =?us-ascii?Q?EEYHa4MWJkyLRr+biaR5U163cIflXJ7mj3MrDbRMCzPVi0zyfZ6EWZ2Yy7uq?=
 =?us-ascii?Q?MZmDBW1A04V8IObgMcmOoD8LSCziCoIkqjXw8Co5KQb3Nun960fbs+SM3+b8?=
 =?us-ascii?Q?3D0P4rXvOzolqXJjySxkBz3Xi+8pxJtU9L5MXdxuEf0SuXAgcKWvf/Pi91XU?=
 =?us-ascii?Q?noUCS5Ju/ltg+kLK+1BohrCvxHkYfygXgQB5pavwI6JcRtblRxAqnN5MqvYG?=
 =?us-ascii?Q?g/61BQOUDNguUcc8iPWAZNSGXr2Ck7kPPEVUEC5floBrwAwNrRck60L3npqm?=
 =?us-ascii?Q?CEat9iAWqhOgD1/R0/UvdIa4jQYxFI5WABMYpEkb/hdt4fGc8PtH+JwiLhZs?=
 =?us-ascii?Q?m/dvfpvu4iaOFg6tQd0leGGJ2to1Sczao+JfHNiBxTwmdRMF6YsHOVgZO+bv?=
 =?us-ascii?Q?5oD2QM0BWZJcmD0UytRnUP1TOyZMEswMUxw3J8ViKLe4fchcnBmRL1pjyN4v?=
 =?us-ascii?Q?WGxIn7emI+0/ylCiJ5VDKV1SMnGkR+xmvj9+vbZZy7MtWRLWxZMLpU9Z/M1B?=
 =?us-ascii?Q?22xvIDVYJiFKduHtCkjjQtHGa4erRlKupN8i1Mq3HiQj8dR5tgbrylFAN3mq?=
 =?us-ascii?Q?AAtjbj01zyZ0EWfsgBNUUi7ZbK7vO6yED/JKLudNH4OrVCgHRtZ19OqOdbsU?=
 =?us-ascii?Q?vvZWzdEKk2mlA/vwrQiOzJKaefsLqGKvHA+BHYoA2JyAV6XIVbEtcm8ZyWh5?=
 =?us-ascii?Q?dw=3D=3D?=
X-MS-Exchange-AntiSpam-ExternalHop-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-ExternalHop-MessageData-0: 9QFi7qLkTVHgqDDdUIM+o5dv0hDsVc0QGO/7UJokEQ3lzx7tVgLc0ovhnbTnAQzsIzL2TSm9Jgj1kkMSBAxkQfo8LWr+QqinjNLGlrAYc86pc6k3uOLrNrzg4r+GZljWs/grcVv3nAobdHZguWWAoZreEcKX8nhVii5vKfJyKWiMh/yBT1VhZlDaO8QAdFwDoXFme92030vq1M2DsUAv+KbVyrcqLAV0UA51VFPeduuL2Fz/htfxgrbQGW8CRCl0HMphiSniQBHS3Ir2Mn/KLTrvbk9Uq6Gd6KZe0yXrZFVkgJGPW+dQ7h3pIAvulfGDZ/cNxS6RMT5xpZ3R2mDZM01OSxMKwhERJTythO4dqc7O79mJgwEZcNcUvHaZhzjlRZF9lfj5L6Y4+WwLMHkZlKr0UarlLn0r+pDq/XhSPCABDKeo5K42m1Bf0SHVEYIjLxLCjxeH7+bw7lnNX2KfhJb0lEVY4FaZb18R3zMWNrBlGMm+5UojxRfQLyBurpB1TmmBr03lX293DEjlvmaWlHcpj+jZXUgQJjS3jbOD4D1mlke3yRj3NcjOuuYiSXfZw3He4k32PUS3bWvD6i/dVFEzs8aQRBKoOjuFi32Yp9+alPbVSAUIHs9/MyTbxOS0I/55T4X729+zftZqh/tEh0XeM7eJ5ONzCtv7kE3hDTooWjZe17OZVfAZzDoDtV2gOPGMnAXaUddbP5fYNQJZaKLQrGPaqcWyA+deAqI1G98MrnQVKh4UMetWLb9AfpjOrdchRUkRw5Kv6PjE36BQUPbehpOYaATtrfs8M8I3YpjQE5E2xb0XRvYmAQyrNYjcR5NXYR5PWJS+Vm3J5zWOUSCUpKXMphNYTWwu6xC7ZRNy47dNrGrEE8xkhkli7ppnLB2uNixo7uzofvCn/rD/DSlqqfic0CIk3afOFYl/7Do=
X-OriginatorOrg: oracle.com
X-MS-Exchange-CrossTenant-Network-Message-Id: bc55b3ac-aeb4-4153-ab5b-08db639b0029
X-MS-Exchange-CrossTenant-AuthSource: SN6PR10MB3022.namprd10.prod.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 02 Jun 2023 18:55:57.8267
 (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: xJkLITJpxWLSLZ+mltcpcuvoZP/gkzBMNQHD68gGKc8iG78Yhi+REjl39Vcen3k5IjPcF0QMDNguSreMpRmVTw==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: DM4PR10MB6015
X-Proofpoint-Virus-Version: vendor=baseguard
 engine=ICAP:2.0.254,Aquarius:18.0.957,Hydra:6.0.573,FMLib:17.11.176.26
 definitions=2023-06-02_14,2023-06-02_02,2023-05-22_02
X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 suspectscore=0 phishscore=0 spamscore=0
 adultscore=0 mlxlogscore=999 bulkscore=0 malwarescore=0 mlxscore=0
 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2304280000
 definitions=main-2306020145
X-Proofpoint-GUID: UKmZSU4sQejAPCwmry96nA0SSd7IzkPf
X-Proofpoint-ORIG-GUID: UKmZSU4sQejAPCwmry96nA0SSd7IzkPf
X-Spam-Status: No, score=-2.8 required=5.0 tests=BAYES_00,DKIM_SIGNED,
        DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,RCVD_IN_DNSWL_LOW,
        RCVD_IN_MSPIKE_H5,RCVD_IN_MSPIKE_WL,SPF_HELO_NONE,SPF_NONE,
        T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6
X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on
        lindbergh.monkeyblade.net
Precedence: bulk
List-ID: <linux-kernel.vger.kernel.org>
X-Mailing-List: linux-kernel@vger.kernel.org

* Yin, Fengwei <fengwei.yin@intel.com> [230602 04:11]:
> Hi Liam,
> 
> On 6/1/2023 10:15 AM, Liam R. Howlett wrote:
> > Initial work on preallocations showed no regression in performance
> > during testing, but recently some users (both on [1] and off [android]
> > list) have reported that preallocating the worst-case number of nodes
> > has caused some slow down.  This patch set addresses the number of
> > allocations in a few ways.
> > 
> > During munmap() most munmap() operations will remove a single VMA, so
> > leverage the fact that the maple tree can place a single pointer at
> > range 0 - 0 without allocating.  This is done by changing the index in
> > the 'sidetree'.
> > 
> > Re-introduce the entry argument to mas_preallocate() so that a more
> > intelligent guess of the node count can be made.
> > 
> > Patches are in the following order:
> > 0001-0002: Testing framework for benchmarking some operations
> > 0003-0004: Reduction of maple node allocation in sidetree
> > 0005:      Small cleanup of do_vmi_align_munmap()
> > 0006-0013: mas_preallocate() calculation change
> > 0014:      Change the vma iterator order
> I did run The AIM:page_test on an IceLake 48C/96T + 192G RAM platform with
> this patchset.
> 
> The result has a little bit improvement:
> Base (next-20230602):
>   503880
> Base with this patchset:
>   519501
> 
> But they are far from the none-regression result (commit 7be1c1a3c7b1):
>   718080
> 
> 
> Some other information I collected:
> With Base, the mas_alloc_nodes are always hit with request: 7.
> With this patchset, the request are 1 or 5.
> 
> I suppose this is the reason for improvement from 503880 to 519501.
> 
> With commit 7be1c1a3c7b1, mas_store_gfp() in do_brk_flags never triggered
> mas_alloc_nodes() call. Thanks.

Thanks for retesting.  I've not been able to see the regression myself.
Are you running in a VM of sorts?  Android and some cloud VMs seem to
see this, but I do not in kvm or the server I test on.

I am still looking to reduce/reverse the regression and a reproducer on
my end would help.

> 
> 
> Regards
> Yin, Fengwei
> 
> > 
> > [1] https://lore.kernel.org/linux-mm/202305061457.ac15990c-yujie.liu@intel.com/
> > 
> > Liam R. Howlett (14):
> >   maple_tree: Add benchmarking for mas_for_each
> >   maple_tree: Add benchmarking for mas_prev()
> >   mm: Move unmap_vmas() declaration to internal header
> >   mm: Change do_vmi_align_munmap() side tree index
> >   mm: Remove prev check from do_vmi_align_munmap()
> >   maple_tree: Introduce __mas_set_range()
> >   mm: Remove re-walk from mmap_region()
> >   maple_tree: Re-introduce entry to mas_preallocate() arguments
> >   mm: Use vma_iter_clear_gfp() in nommu
> >   mm: Set up vma iterator for vma_iter_prealloc() calls
> >   maple_tree: Move mas_wr_end_piv() below mas_wr_extend_null()
> >   maple_tree: Update mas_preallocate() testing
> >   maple_tree: Refine mas_preallocate() node calculations
> >   mm/mmap: Change vma iteration order in do_vmi_align_munmap()
> > 
> >  fs/exec.c                        |   1 +
> >  include/linux/maple_tree.h       |  23 ++++-
> >  include/linux/mm.h               |   4 -
> >  lib/maple_tree.c                 |  78 ++++++++++----
> >  lib/test_maple_tree.c            |  74 +++++++++++++
> >  mm/internal.h                    |  40 ++++++--
> >  mm/memory.c                      |  16 ++-
> >  mm/mmap.c                        | 171 ++++++++++++++++---------------
> >  mm/nommu.c                       |  45 ++++----
> >  tools/testing/radix-tree/maple.c |  59 ++++++-----
> >  10 files changed, 331 insertions(+), 180 deletions(-)
> >