Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::3:2 as permitted sender) client-ip=2620:137:e000::3:2;
From:   "Liam R. Howlett" <Liam.Howlett@oracle.com>
To:     Andrew Morton <akpm@linux-foundation.org>
Cc:     maple-tree@lists.infradead.org, linux-mm@kvack.org,
        linux-kernel@vger.kernel.org,
        "Liam R. Howlett" <Liam.Howlett@oracle.com>
Subject: [PATCH 12/12] maple_tree: mtree_range_walk() clean up
Date:   Wed,  1 Nov 2023 13:16:29 -0400
Message-Id: <20231101171629.3612299-13-Liam.Howlett@oracle.com>
In-Reply-To: <20231101171629.3612299-1-Liam.Howlett@oracle.com>
References: <20231101171629.3612299-1-Liam.Howlett@oracle.com>
Content-Transfer-Encoding: 8bit
Content-Type: text/plain
MIME-Version: 1.0
X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-MessageData-0: =?us-ascii?Q?pahLqxWCI099x1hySxQEzARJBOF3YJBY9Eg4udVhr3tZTyRZ7aMFr8dxcQoq?=
 =?us-ascii?Q?lIcy6z8SV/O0XC5wtNRxYYTyBbl2OtMiZAGN1vn8/W56kxBasbZd+O2l591d?=
 =?us-ascii?Q?0wB+ZBmCFuKucJoVPu4/KP9VvfDg249Vq70LPrFRiZGrzGURNCo6ov6VE0Fb?=
 =?us-ascii?Q?4wwFjayXf8ofd+ge3ASatD4b623BNKky7UtWQX2j9u/8TUH7SFMkvr2Se+LS?=
 =?us-ascii?Q?26P4UhQMBu3mwnuNN5txoo+EwePO3Sulux+PXLD/ivHxExHAeZtOd+jVhejI?=
 =?us-ascii?Q?OrE12LHFgGXWfuSFT7lhB8JsFhF0mxjBsxe6dYj0D81pfq9hEOV9zJKfx/ZF?=
 =?us-ascii?Q?+S1lmInCbhIAUHPdpKz6DGQTMjLmZvkzbhu/7gfLBnK6zLxLACndPWykJdCh?=
 =?us-ascii?Q?WjQkuA4QtNP7acW9kdUARSUQ1UK7h/tk1IzPMnA3YQXgjtl6YTj5RkX0ZnUb?=
 =?us-ascii?Q?KyujunhDGGb2aAn2YjwwQ8D9YDnmJ0YdOMhH0pHkSErgOocgwSfF5gXZ0IlI?=
 =?us-ascii?Q?mfa3U7o/xqS1OS7I4DwoGCFK2GeIYSh1gagdT/cAE2JZBTtJGygBtGoiyoBd?=
 =?us-ascii?Q?VaJtsCPyFy051pYmkufOwYt3e0p4AgEM3v3HUuoe0xWAiX/OIdksS8mHHKLW?=
 =?us-ascii?Q?ipFHTQ2C/qlPt7C3C+ansoPxsuMysiSecSDJzc6INR7zeBjjsG0JqDTL3pai?=
 =?us-ascii?Q?mAQJq5njDUHQA4wUoMKy85nXOnvtRgEpGURhfaAW3BMNIED6a9MDo9SsBKni?=
 =?us-ascii?Q?CGJeig2CLVCrpuxjcr5Uizk5DwHx1jikdQjcl09VswQCbySs/l4U9CEnJ+BB?=
 =?us-ascii?Q?f6HKFxwyuuY37ZQtKKTzMJ30U8EibNhwboeC3QpO2y/ccvb1SMSVZaazRmrD?=
 =?us-ascii?Q?UUEup+NG4QYJ9BjRq7DJbzvaJvysCNw466uR9UMmDmRwOS4JWCPyYCrF7wk1?=
 =?us-ascii?Q?swqwS0RKhJUz6qGdfHaJ1q9zmgMG2NhPns0mVhWMqs2LCafeIk4BJ7mXeQwc?=
 =?us-ascii?Q?auBEpOCG9a6Mb0qToGC8x50yVAexkubDSykmCTl0x5LiJ0JKYiY7QVstmoBY?=
 =?us-ascii?Q?rxiK4DK/fOQJ+AOi0IHgxH6h+pEcTI4DF5VIYVWJh43xgMddwiS39GKu5Owp?=
 =?us-ascii?Q?gJl9U7M6IoLf6YxbdoIp73nkk3G9xksn/8t9brW2N8kOQNF5Q+ODHaxOVn8U?=
 =?us-ascii?Q?dVk2AY8ZoPRzxC+dfMPUHXB+1H02L5ZfMPHHnZ3h1nBPApUq/HcqkRKpHrxA?=
 =?us-ascii?Q?1+ABgoeobQKkHqhZcIgJwIJ2uXKcbl9NeGHVg8y6GGElVXV/u7+LQVHH2aSo?=
 =?us-ascii?Q?IPphUQTOTLVNHhCJkjKfG+aHNwmRb2HTXycrMKwvnN0OrAV8PqQILHDtUZKa?=
 =?us-ascii?Q?J7NnZl57dKBHcG4kn/P2PaQ4XIuwqxS1ktN7xPvvz7hubS8YyRSaBw5jA1eY?=
 =?us-ascii?Q?c0+NnzyDxwMwQ1m7Ax8X7pr/M7Z9SolcucJoqPupCGUzXB6Y/ondRDJV7FMO?=
 =?us-ascii?Q?kIUlNe0Patv2wMXA70tlAJmwkfe6EARDoYjPU3C2B+pbC/YsCHVwlkrQCGCp?=
 =?us-ascii?Q?5gB0/8MF6ZMXXzldl/9GUCxFXd/xgnRsbITLABB6xeBEiUBsEz+a+mXTo51x?=
 =?us-ascii?Q?fQ=3D=3D?=
X-MS-Exchange-AntiSpam-ExternalHop-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-ExternalHop-MessageData-0: VEFy1vQKs9VHPfT7LbpukqA+HEgKE4o3X9roLYFlzxPiwnxQ7kGI51JbY9bNPW0YaNgWQlwuJ4QfWulPAGd3Qdvq3QjXH3RmczbDu/1HeDck6skXoxgVngInSqnnMAtPmezZzfwrX/4WfMoBDUIVKAF+1RzQo8T5UrYdtLz/5s9jWdqamrrq63KZIXdFBJMmTTkU6l4rmJTcLORD3y3RfrL1lf6BYyi70Le9guTDVKtPnZaglrycoywYNpsMbGHoOYG4UaPx0PRioRFF5/F9aGE6QJ2bqfK/N83pFs7MDKH3YtvWxZx2qQFJvPK1KwvxINm88OnGh3axfrcw0+96NgSv7SgXrBmZW29D+N0FsaozO8mlWgsmjXiDoatjnPDHdHvrYblpR/Inkg+poyv5RuZW15xaXaXP/k30KtHqDTGJacPK+anSctRciBmQx8O4i7CvOcuIahevCkbW85J3iNXEU2c259s3OroocHS1wCpJO4mRX8YAxLdVCzxTd9bN2qJlHYZg6pGtCLJqptnHCRZuFrQhiGXpnCKRvz/eV/nNAH/MlK06PlSGf+/TJeHEcUwr9dUGowNO5YnWiGyO99zhlDg9M14U1LSvDuhifGQn4tB9rrtuSWff6bDMi6HX7baHctR4GmemvoOQgnv+G3AwIao7j5ZOVuHHbYYdch1g4liUbtTeQKtcXsyoZvWsTLuPqBwykCrbgG8edcvvC861ZLK0xKi9A7BRFw1EZuy4i1xrJTU1XgOn4myR8f08IIxuxQR++eM4HIoZXUqqKCnxuYPqICCj2GxajsH+jCYAnoQPQFXb6dnvpa97jFbjfsa//ekzg4aqSM31A8konjYKAQYVmoGzqGMdGvRLQnE91mGk403LyaY0lIwAR5HanRGk6ozxuKuLLHHtAeJKyw==
X-OriginatorOrg: oracle.com
X-MS-Exchange-CrossTenant-Network-Message-Id: 6c144100-b373-410c-021f-08dbdafe5af2
X-MS-Exchange-CrossTenant-AuthSource: SN6PR10MB3022.namprd10.prod.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 01 Nov 2023 17:16:58.6094
 (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: j5apUjXyESkK1DlG1QfIpUB3sHERjOIH9+onRmiJczK3Um/Zqsse7shYD83XKg8ZioFu2dg7YAhpD7owyBVO5g==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: SA1PR10MB7684
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-11-01_15,2023-11-01_02,2023-05-22_02
X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 bulkscore=0 suspectscore=0 mlxscore=0
 spamscore=0 phishscore=0 adultscore=0 mlxlogscore=999 malwarescore=0
 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2310240000
 definitions=main-2311010134
X-Proofpoint-GUID: Pd4JlmodrTGVuawo9VVTCDlHxG0dvDp-
X-Proofpoint-ORIG-GUID: Pd4JlmodrTGVuawo9VVTCDlHxG0dvDp-
X-Spam-Status: No, score=-0.9 required=5.0 tests=DKIM_SIGNED,DKIM_VALID,
	DKIM_VALID_AU,HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI,
	SPF_HELO_NONE,SPF_PASS,T_SCC_BODY_TEXT_LINE autolearn=unavailable
	autolearn_force=no version=3.4.6
X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on agentk.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 (agentk.vger.email [0.0.0.0]); Wed, 01 Nov 2023 10:18:00 -0700 (PDT)

mtree_range_walk() needed to be updated to avoid checking if there was a
pivot value.  On closer examination, the code could avoid setting min or
max in certain scenarios.  The commit removes the extra check for
pivot[offset] before setting max and only sets max when necessary.  It
also only sets min if it is necessary by checking offset 0 prior to the
loop (as it has always done).

The commit also drops a dead node check since the end of the node will
return the array size when the last slot is occupied (by a potential
reuse in a dead node).  The data will be discarded later if the node is
marked dead.

Benchmarking these changes results in an increase in performance of
5.45% using the BENCH_WALK in the maple tree test code.

Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>
---
 lib/maple_tree.c | 27 ++++++++++++---------------
 1 file changed, 12 insertions(+), 15 deletions(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index a91adaf17306..56cc8278260f 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -2796,32 +2796,29 @@ static inline void *mtree_range_walk(struct ma_state *mas)
 	min = mas->min;
 	max = mas->max;
 	do {
-		offset = 0;
 		last = next;
 		node = mte_to_node(next);
 		type = mte_node_type(next);
 		pivots = ma_pivots(node, type);
 		end = ma_data_end(node, type, pivots, max);
-		if (unlikely(ma_dead_node(node)))
-			goto dead_node;
-
-		if (pivots[offset] >= mas->index) {
-			prev_max = max;
-			prev_min = min;
-			max = pivots[offset];
+		prev_min = min;
+		prev_max = max;
+		if (pivots[0] >= mas->index) {
+			offset = 0;
+			max = pivots[0];
 			goto next;
 		}
 
-		do {
+		offset = 1;
+		while (offset < end) {
+			if (pivots[offset] >= mas->index) {
+				max = pivots[offset];
+				break;
+			}
 			offset++;
-		} while ((offset < end) && (pivots[offset] < mas->index));
+		}
 
-		prev_min = min;
 		min = pivots[offset - 1] + 1;
-		prev_max = max;
-		if (likely(offset < end && pivots[offset]))
-			max = pivots[offset];
-
 next:
 		slots = ma_slots(node, type);
 		next = mt_slot(mas->tree, slots, offset);
-- 
2.40.1