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;
Message-ID: <7a5dc9ce-b58f-e1b3-db1a-d00a8a556ae5@intel.com>
Date:   Fri, 2 Jun 2023 16:10:40 +0800
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:102.0) Gecko/20100101
 Firefox/102.0 Thunderbird/102.11.0
Subject: Re: [PATCH 00/14] Reduce preallocations for maple tree
To:     "Liam R. Howlett" <Liam.Howlett@oracle.com>,
        Andrew Morton <akpm@linux-foundation.org>
CC:     <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>
Content-Language: en-US
From:   "Yin, Fengwei" <fengwei.yin@intel.com>
In-Reply-To: <20230601021605.2823123-1-Liam.Howlett@oracle.com>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 7bit
MIME-Version: 1.0
X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-MessageData-0: =?utf-8?B?cnU3cThlZ2h0ck85YjdFbnBibiszVHlLcHdadURFZHZnVWdGbEFIeXRldUFR?=
 =?utf-8?B?VmdjRGkzSUNDQTc3eSsvRVhhY01peUFsbG4wdk45N2czMEJtWFVCR0o1eWdI?=
 =?utf-8?B?T2Z2NldSL091N2NneXhROEhUQ3JXSUFiOEpzeUh3MGlveERrcGxZNW5nellX?=
 =?utf-8?B?VEtNVUkrdHFlUGdhUGJOZ0tvU2xsa3FuYnFrZ3pVLzhmOWdlVHU4TjFrVUFh?=
 =?utf-8?B?d0owTEhaaGQyNCtzdWNsT25nN0lYeFZNSDlFMzhSeXdZbkVFQXdZVnBORjNh?=
 =?utf-8?B?eTg2N3p0SmNMQmw3YVcrRitWR3F5djI1L3lwaHJodDdIWU51VUdBVWcvb1N3?=
 =?utf-8?B?MUFxeGVvTTA2a2ZYcStCOFh1VGExaThQS3VDd21yVzVsQ2Z0ZW9DeFRUcVVr?=
 =?utf-8?B?NmJjTjNCYWU4c09DbDMxY3JXaEdzSmxoZU83clV1YnkyYzhSZktMbmdJN0w4?=
 =?utf-8?B?amlsOCtsZkt4b3dsVVZHK1Brb1Z1d0JKTUJEbkpNdndYOEl1aGVLeGJ0WWJY?=
 =?utf-8?B?NWhSR2lpeXBDaCsxTFJpRkI2RTlGZGh1WWNlaTRmTVZvUFRYWWQ3VjZCckpj?=
 =?utf-8?B?QzUxTFFwMVB0cG40UFN1aXFEeHZNY09pMUZ3Z0Eyc3BhS0FEcFZXOXM0N2dH?=
 =?utf-8?B?YUtaNnNKQVlVTjJVTHArRjdza2QyMzZkOGJjRC9ZUVJJcUZSbC9GcXUrZ3hL?=
 =?utf-8?B?UlNGM0NDdlFlNCtPcDUzNmN0NVJEVnplM1V3SC94TnB5SWNUUDQ0d2FGUXhx?=
 =?utf-8?B?aGF5RWpxMXJYTGdIekVxUmNSczBLcDl1TElmYjkrNmhIOWpSbmFvejZEZTdq?=
 =?utf-8?B?UlNWdnVjdWFuOXRuWk5VTUVPeU1RMXJ2TUsxUTNIcE5ZOEVydGtRUkdEbXNR?=
 =?utf-8?B?bUNSdHNhaVplS3lPQjZvRnpiOHQ2VHdLbGxPM29KNnFCSXBBeE5lZXN3Zk4w?=
 =?utf-8?B?YnpVbWsxNStXL0RiN3B0NUk5SmRjVEYvbmpUd2hMZkhaMnVKNkdLYkdtOHlj?=
 =?utf-8?B?bUJOdmZUTDR5SkZkTCs3ZWhrOUtiVm5GNUZiWHEzbVdJTisxZDJPOHVJWmVj?=
 =?utf-8?B?VVl3UDNobnZXdStQTFVuOUEyM295R0hqRmFZTEtmQ1AwcVJ3RWRyYmRSSXl0?=
 =?utf-8?B?aHRtZmViRWQyRHpDb0l2SWpMcTczVEJzbDI3ZDhMWFl2V3pZaEg3OHNpcy9J?=
 =?utf-8?B?OUpKeDVlQitnbGswWFl2aVZqVzkzMlNTN3hhd3RucjhqdWNsb1ZBZjR5OEVX?=
 =?utf-8?B?VXcwRkwwWmxsbFhwL0ZnUU5nL3hDVDhKUnZtS3EvVmhaZEMyMUNjRGhzUy9Q?=
 =?utf-8?B?VENNTmxhaFc2RDBzTks5RzlkcUFiZmhXMVhHa2pML0NTcThVMHRpR3c1OEMv?=
 =?utf-8?B?TDRaSHl3ODJucVoyRkYwTXRQM1lJdXVTdlRqK1lQV0hBUlhWRk51RzRmbUZm?=
 =?utf-8?B?bzF1c01CaVIzMW1yRmdlMEw2cENRZkRnUysyalc3d0ovOWdtZ2JTaDBPZXkz?=
 =?utf-8?B?aHl4R3oyRThMdFRoMVgrYlBvdkM3aFlZZWV3eWlUeG96WnhqZ05JcVhEZDA0?=
 =?utf-8?B?dUcxSVpJcGdjb3lxU05hMUlkT1pzclRZOWdXNFQ0cU9uOVF4TVNKWEtpRmdO?=
 =?utf-8?B?ZzlFUGE3Slp3c2ZnTmVycStiRzJlUlZoM3RPUGVCVFNnTCtnNXFoeWo4a1hm?=
 =?utf-8?B?K1hNNjZhdFRpOENmbUJoUWF6cmxzRDRMRk1NOVM1Q0xvajdrLzZoUGw2ekk1?=
 =?utf-8?B?OVhpMWx1dW90M2wrNzFtNmxSb3MvdVQvSmVYc1Rmbk1nVThPay9OUWJubENi?=
 =?utf-8?B?Q1A3a2YzcWZ3NlU5YnRDdnAvTUZhMjQxd3NKdEFRTzFQaVRQR3Z2a2RGNmxV?=
 =?utf-8?B?M1hMZVpQaHB6WS9ETjBSRUltYTRMM1lhZHZrK3N6emQrTVhvNFV0Z3AwZ2Ey?=
 =?utf-8?B?U2tScHdxdE5SZFFCQ2Zqd01kS3VOY3NsbkZEMzBQZnUxRGVRMDFaZTY2bXJ5?=
 =?utf-8?B?aHdkc2k5K00vUVdpVXc2aDc3TS8yWVdOOXh2MlZybWhkakdwbHJIYkhKRmVG?=
 =?utf-8?B?NFZ2MDBSTHNnL3pjdlRJVDRNbGphdm14dVFML3VmRCs3SzhUV1Z0a0dSdlF3?=
 =?utf-8?Q?eFpzWRJPQP0b4x5TXOAdMTejk?=
X-MS-Exchange-CrossTenant-Network-Message-Id: 481ecefb-62f3-49f7-6b30-08db6340df54
X-MS-Exchange-CrossTenant-AuthSource: CO1PR11MB4820.namprd11.prod.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 02 Jun 2023 08:10:48.1594
 (UTC)
X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted
X-MS-Exchange-CrossTenant-Id: 46c98d88-e344-4ed4-8496-4ed7712e255d
X-MS-Exchange-CrossTenant-MailboxType: HOSTED
X-MS-Exchange-CrossTenant-UserPrincipalName: wEn+kIqNWbNkQq0rDlVm88cWVPOKRddHDJuS7iWFPU4UEX8iQ/0cBA1ajz+jPaX8eiM7YP9QorLw1xGEPocuHA==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: PH0PR11MB4839
X-OriginatorOrg: intel.com
X-Spam-Status: No, score=-4.7 required=5.0 tests=BAYES_00,DKIMWL_WL_HIGH,
        DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,NICE_REPLY_A,
        RCVD_IN_DNSWL_MED,RCVD_IN_MSPIKE_H3,RCVD_IN_MSPIKE_WL,SPF_HELO_NONE,
        SPF_NONE,T_SCC_BODY_TEXT_LINE,URIBL_BLOCKED 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

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.


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(-)
>