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: <a9d2ab1b-23a5-8c06-9f7a-6872c726db03@intel.com>
Date:   Mon, 5 Jun 2023 12:41:37 +0800
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101
 Firefox/102.0 Thunderbird/102.11.0
Subject: Re: [PATCH 00/14] Reduce preallocations for maple tree
Content-Language: en-US
To:     Peng Zhang <zhangpeng.00@bytedance.com>
CC:     <maple-tree@lists.infradead.org>, <linux-mm@kvack.org>,
        <linux-kernel@vger.kernel.org>, "Liu, Yujie" <yujie.liu@intel.com>,
        "Liam R. Howlett" <Liam.Howlett@oracle.com>,
        Andrew Morton <akpm@linux-foundation.org>
References: <20230601021605.2823123-1-Liam.Howlett@oracle.com>
 <7a5dc9ce-b58f-e1b3-db1a-d00a8a556ae5@intel.com>
 <fad3c833-1ab3-2d34-aa85-dcc7c40c3587@bytedance.com>
From:   Yin Fengwei <fengwei.yin@intel.com>
In-Reply-To: <fad3c833-1ab3-2d34-aa85-dcc7c40c3587@bytedance.com>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 8bit
MIME-Version: 1.0
X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-MessageData-0: =?utf-8?B?QkdCYUNYZ0QrbnlORWFnVDhZVkNZKzR5SC9aN1VjVUoremxQS0g3VStIVlRq?=
 =?utf-8?B?ZUdXWHZpalVOM0pNcWtBUVpwMEVjVkYwck5pMzYvdWZvYzV1UVhZby9CbXFE?=
 =?utf-8?B?TTNuNElKWkVJcmpnWXZYYXdSQllxbC9PSkNGaExUeU4yVzYrQkZObjBoSVZI?=
 =?utf-8?B?ekV1UXp1UEZJdUVNamJOTXEreXh0eFYrWi9XaWNkN1k2Mjh4L2k3YlNwenlD?=
 =?utf-8?B?QnA5d3MwbllXVzV6b0tlRVNaay8wWkdjM2diV3BlcER3a1Rzbkt5WmxnMVhH?=
 =?utf-8?B?MXgyMzV4MFpDYjBXdVJ1S1Q0QlVrNFNaWXVNMUxpSi9OSkdwQWxqVmIvdVlN?=
 =?utf-8?B?SWlXcFczMCttTkJDcmlSUFpwWFhoVysyVGpNaVFrcHNwc1lGRU12NXl1aVB5?=
 =?utf-8?B?VXdOOGdkQ2hiYnN6UW5lMHdabWYyanhLOHFCSVZ6T05LS0V3VmdBVUFKSTBx?=
 =?utf-8?B?ZnZSL0xZYldOcWdyc1dlZThxWWE3OTFwM3lUMzg3ZmVpNC8rQXBWbFZWOS8y?=
 =?utf-8?B?djZ3c1F5Ylo2R3J2Q3AzR254RitZa2ZmL0JjclcybTMrcGh6d0N3dXp5ZDgw?=
 =?utf-8?B?WmRTYmpuZTFrRGRxZlY4RHZEODFyVHQzV0RMNmhidi9IYm5RMEM0QWdQRitt?=
 =?utf-8?B?eW5ZMG9pR20xeEJ4b0VsVFYwOTdQL0tXZDVlZGo1cEc2T2ZKaXRpZW55SThS?=
 =?utf-8?B?OXpnS1pFVmpIYVRVZzYyWmc3b01jdTIzeEFEaC9pcHFCbStCZW9zQ2FtZEdQ?=
 =?utf-8?B?Sm5EZUVsTllPamxzelhQRjVFZWxPOUg1bHpVR24xaS9rWkxSWjdiMWFsNVJS?=
 =?utf-8?B?elJ6cTU2YmtZeEdYSzB4TDl6UDZ2ajFCR3VoTFFibkN3VTMzU0puRk1KVHpk?=
 =?utf-8?B?OWh3UGF5MGIvbmRaVHlrcGNFK0w2dmluRUVTUnFNVDZ0VWVSaXlsa3VRa1J5?=
 =?utf-8?B?TmVabXJzTTZUNU5ZVC9rbmdWbmQwVWVEbUdMendOQnB2SUdwMjc3MEtaL3lM?=
 =?utf-8?B?ZERaRCtJSHFSSWIrMXFJNklOYXFiMFNKeVlQSDBiNXRPTVJqTGd3bWdMRVpq?=
 =?utf-8?B?U3U0YjdJTUpxZmhhZDI1alVieFJwTjZ5Nk5hcllXUW5zeWFyV2d5djh6ZkQ0?=
 =?utf-8?B?SEErYlVTN1d3WXZhMGRieFJTUjJpTHVQZFJoaHpGU1ptVXE1VUdoSFJoTGx5?=
 =?utf-8?B?VElPeml3UGlOWlRJY1BSdVYwM2ZQK2c0cDdRQUZkcGplV09xa3pOZ3VSZGxJ?=
 =?utf-8?B?aGh4Qm5ScGZYWmJjNlA3a3Z0RWhnVEdlQU5DRlREaFFkU0NJa0IzYi8zYXor?=
 =?utf-8?B?NFZpNHgwc2dTcGd2YTdGNEpnYzRuVFpza1N0WVdWRHNZYXNFUmM4NmtNeHpL?=
 =?utf-8?B?bzZDWXJWdy93dlVZUGJXK2lSS0hjaGFGV0Z1eFExaE9vNXFiN1hHR0pFTG1D?=
 =?utf-8?B?bk5yNjdnTXg0TEtxQjFITDZEZXRoc0VsV1ZtU3FlckpZOXN6a3ZabG1DUlE3?=
 =?utf-8?B?ZGpRcHBRRjVFVm42MGd4RDlSejVLK1pzOFRxVDFsMXFEa0poUFBQOFhKa2xU?=
 =?utf-8?B?bzA2VEJCWThpc0NsYlU1MGpzWjcxYlRtRk5kSDRoTWNGK3MyUE9VbXA0cDNV?=
 =?utf-8?B?UThoV2NFbkJseHQ1a1JkY3ZQZ0g3cGFQQ2dPN3BGSnNpaENQUXNHUXVma2dx?=
 =?utf-8?B?eUQvd2l3U0RxNTBCczY3SHB3Y09NRXE4dFd6a2NTUVJoOTh1T3QwTEtiU2xK?=
 =?utf-8?B?c28xcXA4RldQbW93bmtpU1o5d1RTaGtvSFlDT1BHcSsySmhtTkhmY1BSYU1V?=
 =?utf-8?B?YnpaNkh4S1QrK0RRa25GeW5kQkN5SXc0Ullmc1lxc0gybm14bTFSQ2JJbGJa?=
 =?utf-8?B?cHcxVHFEMXp5TDlyMnNiTnBRYXY3bE54SDdJaGZzZEpJSkhqUkI5d3BxaVh1?=
 =?utf-8?B?VlJJbXNmRFZXcjNGcnB0T2ptSitHNnNkSFdiODFnSmRWdFNtV3V0T1h4UWl3?=
 =?utf-8?B?M1JrVWFTbXRtL2hZRmcrM1FaUWo3TXY2dnYzVjlxSjRqZDBxNjZoZUNwUFdz?=
 =?utf-8?B?eHl3TTBTQTNFQUpmQTljMzZwVTNVZHpIcEM3RzlVQ2lsNWJiMWVvQ2xGMFNF?=
 =?utf-8?Q?aq179+AAXyFrW9mHXZYcvcVKd?=
X-MS-Exchange-CrossTenant-Network-Message-Id: 2e4172ac-8b91-40ca-1e03-08db657f1967
X-MS-Exchange-CrossTenant-AuthSource: CO1PR11MB4820.namprd11.prod.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 05 Jun 2023 04:41:16.6117
 (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: aM34Bsu7Pf5KNu+dAcowx4syy6ncv946DTtYK+e48sLlSX37D23+AUo0fdnv4YBiz7DyMqkA+EQiaO5KgFf92A==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: DM4PR11MB6501
X-OriginatorOrg: intel.com
X-Spam-Status: No, score=-4.5 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,SPF_HELO_PASS,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

Hi Peng,

On 6/5/23 11:28, Peng Zhang wrote:
> 
> 
> 在 2023/6/2 16:10, Yin, Fengwei 写道:
>> 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.
> Hi Fengwei,
> 
> I think it may be related to the inaccurate number of nodes allocated
> in the pre-allocation. I slightly modified the pre-allocation in this
> patchset, but I don't know if it works. It would be great if you could
> help test it, and help pinpoint the cause. Below is the diff, which can
> be applied based on this pachset.
I tried the patch, it could eliminate the call of mas_alloc_nodes() during
the test. But the result of benchmark got a little bit improvement:
  529040

But it's still much less than none-regression result. I will also double
confirm the none-regression result.


Regards
Yin, Fengwei

> 
> Thanks,
> Peng
> 
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index 5ea211c3f186..e67bf2744384 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -5575,9 +5575,11 @@ int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp)
>          goto ask_now;
>      }
> 
> -    /* New root needs a singe node */
> -    if (unlikely(mte_is_root(mas->node)))
> -        goto ask_now;
> +    if ((node_size == wr_mas.node_end + 1 &&
> +         mas->offset == wr_mas.node_end) ||
> +        (node_size == wr_mas.node_end &&
> +         wr_mas.offset_end - mas->offset == 1))
> +        return 0;
> 
>      /* Potential spanning rebalance collapsing a node, use worst-case */
>      if (node_size  - 1 <= mt_min_slots[wr_mas.type])
> @@ -5590,7 +5592,6 @@ int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp)
>      if (likely(!mas_is_err(mas)))
>          return 0;
> 
> -    mas_set_alloc_req(mas, 0);
>      ret = xa_err(mas->node);
>      mas_reset(mas);
>      mas_destroy(mas);
> 
> 
>>
>>
>> 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(-)
>>>