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:   Tue, 23 May 2023 13:54:51 -0400
From:   "Liam R. Howlett" <Liam.Howlett@Oracle.com>
To:     Peng Zhang <zhangpeng.00@bytedance.com>
Cc:     akpm@linux-foundation.org, linux-mm@kvack.org,
        linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org
Subject: Re: [PATCH v3 06/10] maple_tree: Add mas_wr_new_end() to calculate
 new_end accurately
Message-ID: <20230523175451.unnpbm5ye35h2jbl@revolver>
Mail-Followup-To: "Liam R. Howlett" <Liam.Howlett@Oracle.com>,
        Peng Zhang <zhangpeng.00@bytedance.com>, akpm@linux-foundation.org,
        linux-mm@kvack.org, linux-kernel@vger.kernel.org,
        maple-tree@lists.infradead.org
References: <20230522050656.96215-1-zhangpeng.00@bytedance.com>
 <20230522050656.96215-7-zhangpeng.00@bytedance.com>
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <20230522050656.96215-7-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?wjtlBzcvRk/sueFDZZXhERHmkMFC++39CmTzcNqk2miLQaIoTtSo/3r31vVG?=
 =?us-ascii?Q?VVhQ9jhQHXx4E3XbUwSHbSt1SM3A8x8K7PutJBn2h06vAJA7ciddPhQNrTmf?=
 =?us-ascii?Q?VuWPtPUuaxKDLYq8Dky5aJIGNWmB+CjHTKvdkJURha+sUw12g3Hw43geoCB9?=
 =?us-ascii?Q?5nVk46RACVYzhuVnDLGXnwrAQEOOEVuZwQi5Y2csFE5jDVu5BvWBHMsE8ZJV?=
 =?us-ascii?Q?lECAVSJRNw0eS/OUSB07DyP34GgPUSA4LCTRZmUBJr4jR4B90vnGYR9KDKgP?=
 =?us-ascii?Q?LhUaui0Ki7KAl//wfSu7LV6Rb1/EGextZa9mUtW7LTSuZ7Eo6Cq2b8oxErej?=
 =?us-ascii?Q?U3AzmKJeMgEUPjO71Wb3OCmQrkREI8evjukrUA4UksRdiBUUV5HaNxtvJIul?=
 =?us-ascii?Q?q2pVgzxbjU1M0d1f6kcdpzVpBonR0cnRFSVNDHdgrPUnF1/WxtN6emIBFrR9?=
 =?us-ascii?Q?sjIjWuLaXHf6MO1OrcKU5k1TCvpCNVASBU30SqC0iZslh4NCYakneAoPslXk?=
 =?us-ascii?Q?xGZxEw2CdeYHfOW1P4ObXv/ll/6bS48a8kV+DhRkFqq1VCxvdUztcosr+FhP?=
 =?us-ascii?Q?9hrOTe1V7jnp0kAchUib16wFFhjKnlLKlFqX2hCHMfwueUsK7kLz89/ywKzs?=
 =?us-ascii?Q?bSb1Xk/nzCSrUd+5EYtgku7eNCH2d5rZVKoKvqbOCSdaW3v3hkxdlDeMDh/P?=
 =?us-ascii?Q?s70niZhtDqpE2K2iL9E7PF43ilKZswqgeQyIv7zS5eBaNWIocNC7PIPAXT7Y?=
 =?us-ascii?Q?zFiq0swZ2rGyIslj8gdalw04/6zN5KCVXZkfFZEE3Uf9Ag5J4M+FBAHRyhRi?=
 =?us-ascii?Q?vYXgdxdnDq9xfosHg1D27a/DL2c4u6Q/5LJe/e8g3G2O3iMfE+9TOQLJM78z?=
 =?us-ascii?Q?t5OcfEtJEFN3KlMDqhb8yUAkujgvIiGGnJT8d/opyQwvtqwjh5tzGnsm5Klr?=
 =?us-ascii?Q?gH0+sZmh2gLJW/jCfVd4KhVybm/Ei4XW8OKxmcpDr2f7YBucGoK4/2bNLK+g?=
 =?us-ascii?Q?vKGfm+Q0QNOCY1d6pyzw2GsdvRkib8AU002porKA3G+VCzlu03v1svsEWbwx?=
 =?us-ascii?Q?co24H93fYnLhkWx8E066sLw7LlaIu0yLNMn2LhwZZi7ynMsH8ZHARkuVW/5p?=
 =?us-ascii?Q?6vZh8QKXI0VrdcJb+xIx9R6hKKD1OaVa8OzMmQWYguyjuSLMjrE1fevH7fWP?=
 =?us-ascii?Q?cv1/FpXqEQ0ukgJXfnfnFQoNhtGbJcwweQpL7jmH/mNbFHMz4a21t390R7f6?=
 =?us-ascii?Q?rrAlhCAfWNJ/MWPuNrynQPouXNpHYN52bPkjH37+jAy0LtcNdcEyW0Fx+cH9?=
 =?us-ascii?Q?iKk4vy7UI8gLKwUVouhX/S0RGE1Ap2Sy7Sb9DeQD1hDmEF3J/fIAc1L4zR33?=
 =?us-ascii?Q?btbgyMp70DUVR0Yu3oMpInUjYGCS2Mb/NZP8fXtSUBmIyWtuC1FX2afDE8xK?=
 =?us-ascii?Q?o5DItwJB4uU/l+4CHcAAzFyyMKlv4sNF2QC1SteewJ7Gj8hFN/cERYOftkGj?=
 =?us-ascii?Q?H0px+9hHdx268HVXuVGOZMplVZlXkOZFp3FJrbkCC94UdqzKsf7RPlnvh8ht?=
 =?us-ascii?Q?GmTiGjSldWRqrBhyYpmVhYQvF63cF9T0UYgoTka48ygUalxxQaI4ws1efjFM?=
 =?us-ascii?Q?Kw=3D=3D?=
X-MS-Exchange-AntiSpam-ExternalHop-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-ExternalHop-MessageData-0: =?us-ascii?Q?2XRVQXSJO5EuKts2RcyBO7onM9iBHro38qGiRfFo1rJU36/XtomgHMPB9uz7?=
 =?us-ascii?Q?wmnN34NwygpuDavjg/keGmlw8IbIYY2NfS6aDWO/CkihLMFYtVNy8gkuzRKr?=
 =?us-ascii?Q?gda2CDsIY2A82hmgWkA5jh7t6xeQxeMb0FIwGcSMQx3ehqiGXMVKLjqHqGI1?=
 =?us-ascii?Q?062Fiqa2HUz8vKT175nocpYDZSILvxlmRfX4TMOdUo7fj6dT5JAFGeMOl/2x?=
 =?us-ascii?Q?ZegiJdDSkOyb6m7LMTpHXvJhxZRm4+hXJiCNz0TfBAy3n/6oqRKmWDXvHJNa?=
 =?us-ascii?Q?RbZAKnVK+osr53FmQ63dq5CxEv6iFOyUpCk6d9yv0lBCWU0eRJaWzov7Ty0L?=
 =?us-ascii?Q?z3BErqIu4nWQhpGkAeT6y27a3l6pZLM9Jn7kZuevtJ4ccQA6RJ4Cd3n7rAW+?=
 =?us-ascii?Q?hCjKfTeEdByVAcE9yUEh1Mcm5bDAB5ZagbY/H4+0qS9/f4sF3zxrYdnHDjlh?=
 =?us-ascii?Q?xuA9nw1ilQWjq7m/22ynHFAQcPRGF4KCxIsiyttCZHHgXc1veVFnGjji6yc+?=
 =?us-ascii?Q?Br4qc5GBUrhd2vVpBSLyxNO1/mxxIVroaBHAuy1yRP2anKkk9UVwktZw7n3H?=
 =?us-ascii?Q?CVpuoyKXawziQZB67z22QOMAJEWPct3po9qtVer91fhPYzZcCbHBI1UU2TWp?=
 =?us-ascii?Q?yhv2RxQTeMp/meuC+AtEiCNiv2rGaxLTq+stncftTIitnHBS5idrhlllcaHm?=
 =?us-ascii?Q?QLeBGkW+CnLBXlWlSMkntZxU3vbQo5UsDiuGU219xxj15osgxKMtTJFo1K1G?=
 =?us-ascii?Q?gvsZjJM1JadQbw2DrUgIVQDnGACVCLVjKrCDbV0F5RQRpJXlDJLQul0N7hyJ?=
 =?us-ascii?Q?JPJV02lqLvVzT+NA59muUsZ7wjCzRyoJlBD95QAgCNQwhVob1/7EZm8J73o/?=
 =?us-ascii?Q?MOWSbxDM/bSHqKQME6fEEMMROdCtRhWtFPBxIJTt3/kKlCV7K0MzlWrtTlfW?=
X-OriginatorOrg: oracle.com
X-MS-Exchange-CrossTenant-Network-Message-Id: 5c597670-44fb-45a9-af31-08db5bb6d03b
X-MS-Exchange-CrossTenant-AuthSource: SN6PR10MB3022.namprd10.prod.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 23 May 2023 17:54:54.1075
 (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: YFz8NHBpicG+q/jpHhwH+P3w+i4tUMDBT6gcbmjOi3tbM82y18GdQnldQXZwy0K7HWYKmbhw8Va/Q19Afr7Guw==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: DM4PR10MB5990
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-05-23_11,2023-05-23_02,2023-05-22_02
X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 malwarescore=0 suspectscore=0
 mlxscore=0 spamscore=0 mlxlogscore=999 adultscore=0 phishscore=0
 bulkscore=0 classifier=spam adjust=0 reason=mlx scancount=1
 engine=8.12.0-2304280000 definitions=main-2305230144
X-Proofpoint-GUID: D42mBOz9uKrUqdkMJamNz-xs3fo_-H01
X-Proofpoint-ORIG-GUID: D42mBOz9uKrUqdkMJamNz-xs3fo_-H01
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,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

* Peng Zhang <zhangpeng.00@bytedance.com> [230522 01:07]:
> The previous new_end calculation is inaccurate, because it assumes that
> two new pivots must be added (this is inaccurate), and sometimes it will
> miss the fast path and enter the slow path. Add mas_wr_new_end() to
> accurately calculate new_end to make the conditions for entering the
> fast path more accurate.
> 

Reviewed-by: Liam R. Howlett <Liam.Howlett@oracle.com>

> Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com>
> ---
>  lib/maple_tree.c | 34 +++++++++++++++++++++++-----------
>  1 file changed, 23 insertions(+), 11 deletions(-)
> 
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index 562507979a4b..0550a07355d7 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -4297,6 +4297,21 @@ static inline void mas_wr_extend_null(struct ma_wr_state *wr_mas)
>  	}
>  }
>  
> +static inline unsigned char mas_wr_new_end(struct ma_wr_state *wr_mas)
> +{
> +	struct ma_state *mas = wr_mas->mas;
> +	unsigned char new_end = wr_mas->node_end + 2;
> +
> +	new_end -= wr_mas->offset_end - mas->offset;
> +	if (wr_mas->r_min == mas->index)
> +		new_end--;
> +
> +	if (wr_mas->end_piv == mas->last)
> +		new_end--;
> +
> +	return new_end;
> +}
> +
>  static inline bool mas_wr_append(struct ma_wr_state *wr_mas)
>  {
>  	unsigned char end = wr_mas->node_end;
> @@ -4352,9 +4367,8 @@ static void mas_wr_bnode(struct ma_wr_state *wr_mas)
>  
>  static inline void mas_wr_modify(struct ma_wr_state *wr_mas)
>  {
> -	unsigned char node_slots;
> -	unsigned char node_size;
>  	struct ma_state *mas = wr_mas->mas;
> +	unsigned char new_end;
>  
>  	/* Direct replacement */
>  	if (wr_mas->r_min == mas->index && wr_mas->r_max == mas->last) {
> @@ -4364,17 +4378,15 @@ static inline void mas_wr_modify(struct ma_wr_state *wr_mas)
>  		return;
>  	}
>  
> -	/* Attempt to append */
> -	node_slots = mt_slots[wr_mas->type];
> -	node_size = wr_mas->node_end - wr_mas->offset_end + mas->offset + 2;
> -	if (mas->max == ULONG_MAX)
> -		node_size++;
> -
> -	/* slot and node store will not fit, go to the slow path */
> -	if (unlikely(node_size >= node_slots))
> +	/*
> +	 * new_end exceeds the size of the maple node and cannot enter the fast
> +	 * path.
> +	 */
> +	new_end = mas_wr_new_end(wr_mas);
> +	if (new_end >= mt_slots[wr_mas->type])
>  		goto slow_path;
>  
> -	if (wr_mas->entry && (wr_mas->node_end < node_slots - 1) &&
> +	if (wr_mas->entry && (wr_mas->node_end < mt_slots[wr_mas->type] - 1) &&
>  	    (mas->offset == wr_mas->node_end) && mas_wr_append(wr_mas)) {
>  		if (!wr_mas->content || !wr_mas->entry)
>  			mas_update_gap(mas);
> -- 
> 2.20.1
>