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 11/12] maple_tree: Don't find node end in mtree_lookup_walk()
Date:   Wed,  1 Nov 2023 13:16:28 -0400
Message-Id: <20231101171629.3612299-12-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?zw03HPwY1tnNqKmawLRoO3KebHZf0fEBO88WlQbH2FN9/vCeaLmLQBrLjWyA?=
 =?us-ascii?Q?Nw14QWIxDvGrTc9YQRMzsD19qrNpeMc6uWIUU8T6RyiDAUI45MdivWjdPilj?=
 =?us-ascii?Q?+pqm6+2nOq83N7qorRKkz/Eo2O1rGYuOcfTzzq0nhEdZ2lysXS9jescHzS81?=
 =?us-ascii?Q?IDI+hVnSk3CZApAtq/rmK90h+YwqjdiYPvkCXOJ0rSk0ufwl9ol7Iess5z+h?=
 =?us-ascii?Q?vqYKVe7qpmOFVFck1uTtp9N2CRX1Ci1Qz2sTO/hyHyqgXtzq7bWdBHFk4Cta?=
 =?us-ascii?Q?xisUHOhq/DH0HaAqZ8Zq/d03Z00fKb4+UC1CHp4uwPyOSH++z2VGtQVIy7p8?=
 =?us-ascii?Q?wRl2OK9L2tHiOkQqkkrGVdvCWNIo+BvJLnB7Ir4CRU/sZttxLSCgj2f8k7wL?=
 =?us-ascii?Q?IDs79ApQBZNp//+dXuH7SXDo0++pM4YL6E3Yg3fr7EjJe115R2+PkyA+A6j8?=
 =?us-ascii?Q?0XaKtLO678N9caS43wsvz3JSExN3L9NLgQaLgevp9rmxybT9Hfw5FVUoJo68?=
 =?us-ascii?Q?1gXDKRPZll/9uzdt7cn299H8+VJICmSGdKPiFNJishb7l5zqfir78Xs6GZvy?=
 =?us-ascii?Q?cjQWsGirFjKrA5rxjIL3pskEn1Rec7WuTHK92J4BfQcTmsBAgKnhr85KLCkb?=
 =?us-ascii?Q?yxKpPjqNsCh9yNQwQv1/Iq+tmGppQTq9iMZCp8QR0aeGDDWyYMK/hUFOGpNT?=
 =?us-ascii?Q?TEMMbBFLLEInZUfRR9ygP0FfQ2seSELhikddvQYZ8jA2UYxcXiVpvsazfyDM?=
 =?us-ascii?Q?//4oqms4WyROyT3JVvUmTSeRcAaIi1AqJbyYC0YE2KJ5FxGYa+C6vNgxqq7Y?=
 =?us-ascii?Q?b/Wwi7/IxDMbkaK02epsPTAKPm27wofRwGHVpbDWHYeWLHVzKG/EEdB8fYn4?=
 =?us-ascii?Q?Ta7pV4gSisOQaFYdWndKDAHO/I7bkPL5knsC5CGwDjAtkIfHsBp9fekU3VaX?=
 =?us-ascii?Q?3E4SkACztkoaX1OU2u8ti1BCUql6/y44q6/FhkrvDKG6rzucmbQ9rDQcKTKT?=
 =?us-ascii?Q?+EFiYn0CiQDWdevV441qaR1jydZO74uBG5u9gSZDRdwBKsUgm7+iZucsz8C2?=
 =?us-ascii?Q?V9YeDlYKhqgkreQOoQ519C7xmpH1X9vwnPb780UxJ9tBZrMT0O+0ixruc0FP?=
 =?us-ascii?Q?xj6D6J0Cb8c64blZS61PiW4D1bM980URJufW4KIey4k9Fqao4ZvifKUHXh+g?=
 =?us-ascii?Q?NHx3fXx1jIvlFl8S03k+56sGyE0gVcjdavq1kjBb9LFvoEvq754RFg+Yw+zR?=
 =?us-ascii?Q?FjAreF4q8io61rEnaWGwL70xZn/13A1OL4pzxtvmifgge9kb7OWaQbKnnUlO?=
 =?us-ascii?Q?mBbSYnQ/T3MzNlvCO7+OJKjZNFSDIlZbQcdZ35e49nlGI72ZWBckXJn3LvEA?=
 =?us-ascii?Q?N5YKiZYqkUl8h6EzpTys4a2RTrEobfMr4oNBwnMLyZKUnBegqSsVQWJW+OiQ?=
 =?us-ascii?Q?rEuynP7TQ0T6qW75Y0vnXK6FpmAWucU03Q0dBuUApgRZr8kPRDGUDQkZ4rHh?=
 =?us-ascii?Q?iK+nS7mRqPpvaoCsDLafJMRxkJOpopjLNxOcWZIMt1yirxWBEvgLdpeVHHS3?=
 =?us-ascii?Q?UjUm3auC0rKAiDjabQ0XlMMxkK4lQ4l/odhEGLEJblEa7oIPFP+1zUyihoaY?=
 =?us-ascii?Q?yw=3D=3D?=
X-MS-Exchange-AntiSpam-ExternalHop-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-ExternalHop-MessageData-0: NrK/kCKcCo505tXeHGSCM3ZNZp/WG5BFH92wswuVeaXO7QmM8b6EfsLmX/MjREn6lDV13lwQL5Kz4bIT/NQPYqwDzjj5klGFJy64kLT6xOO3hJdB+tXuoyF5HmAd1bkHwh+UKk0K45I5cXTGOWLvJzx3J8oJWaDtFjnp6VVDIl0+Fl5509ALpGu6puqIoaibuNnI1cjV+DrAedA2xNW/dmUhwT3sq++wU/diJa2agPXYxZItm9fQYxf1vlfp4skGAC0is703GxAYIH9J9USQOCN73yZcKCNptsFYjp2FISekEdO8e8qVb0HOSkduicV7cJYRzkhL5WRSbwN25WFhF7akqkesEyEDRJZ9a64Y5eHi1slrrBgaCrCOgjo4BN6YbXjNZvn5M0PB9G8b3uVPXSSkXFLXlFyq0b5jh5YhkywvbhPHGc4enMW/xpSAH03oaa3jzD3vj7tCdvVgTmwPqJy1qN/Zx7WTcUkQ6TvXqktJTmyRqNevglIQaQhNv6gOpa81hvDcX4Ek2IJVXEGNgfBndZrBBoR0hRvI3RjACgp5v7jwW/iuBKP9O6NVlOgKZrVhm5oxhSPMABHP5DGvPkgn7S74ojZdl7/TW66XQJEL4OFg6Pn7Dme+ouDiO1E0uW6kJJvAyj3CGrteOBcY5DhYnECYVefSlQocpit509KfbswR18IOraP1M/Je2g5brgf9vuYYj+gntYziIIK0BQmsVs8CLl1UB/TxPesmvIZtY5M1+C8yFK5N1aW/xOt0UnWHc9R5lTIpRABUfyoqvYMwsBX3t5ZpCxU7nvQy8K6NvdL8aJSdsG14lNkSnyC5tqt+KSvKCmmGQ+8r1LsX1YSq0XDZOKHBFEAAEmZDdjrZ0QBoV/2dahAvZtR284y5a7ZkLqDq/yZDp+T3zfJ+9w==
X-OriginatorOrg: oracle.com
X-MS-Exchange-CrossTenant-Network-Message-Id: 4876f74d-3778-4315-fac2-08dbdafe59e6
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:56.8727
 (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: zAoH8iucL29OvpAjFYvlzDlJ3ItlcNW68PzoKoLUr7ESiK+hW47ANY58Xka6SiGK2Um4vuhSgSNW3IKbK818oA==
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: Xfg-W5ZBtaBmw_FkDP_lhgHJkXzsx5s3
X-Proofpoint-ORIG-GUID: Xfg-W5ZBtaBmw_FkDP_lhgHJkXzsx5s3
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:17:53 -0700 (PDT)

Since the pivot being set is now reliable, the optimized loop no longer
needs to find the node end.  The redundant check for a dead node can
also be avoided as there is no danger of using the wrong pivot since the
results will be thrown out in the case of a dead node by the later
check.

This patch also adds a benchmark test for the function to the maple tree
test framework.  The benchmark shows an average increase performance of
5.98% over 3 runs with this commit.

Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>
---
 lib/maple_tree.c      | 12 +++---------
 lib/test_maple_tree.c | 21 +++++++++++++++++++++
 2 files changed, 24 insertions(+), 9 deletions(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index e45734676471..a91adaf17306 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -3732,23 +3732,17 @@ static inline void *mtree_lookup_walk(struct ma_state *mas)
 	enum maple_type type;
 	void __rcu **slots;
 	unsigned char end;
-	unsigned long max;
 
 	next = mas->node;
-	max = ULONG_MAX;
 	do {
-		offset = 0;
 		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;
+		end = mt_pivots[type];
+		offset = 0;
 		do {
-			if (pivots[offset] >= mas->index) {
-				max = pivots[offset];
+			if (pivots[offset] >= mas->index)
 				break;
-			}
 		} while (++offset < end);
 
 		slots = ma_slots(node, type);
diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c
index b82c02f15380..d36dc64a93e4 100644
--- a/lib/test_maple_tree.c
+++ b/lib/test_maple_tree.c
@@ -42,6 +42,7 @@ atomic_t maple_tree_tests_passed;
 /* #define BENCH_NODE_STORE */
 /* #define BENCH_AWALK */
 /* #define BENCH_WALK */
+/* #define BENCH_LOAD */
 /* #define BENCH_MT_FOR_EACH */
 /* #define BENCH_FORK */
 /* #define BENCH_MAS_FOR_EACH */
@@ -1753,6 +1754,19 @@ static noinline void __init bench_walk(struct maple_tree *mt)
 }
 #endif
 
+#if defined(BENCH_LOAD)
+static noinline void __init bench_load(struct maple_tree *mt)
+{
+	int i, max = 2500, count = 550000000;
+
+	for (i = 0; i < max; i += 10)
+		mtree_store_range(mt, i, i + 5, xa_mk_value(i), GFP_KERNEL);
+
+	for (i = 0; i < count; i++)
+		mtree_load(mt, 1470);
+}
+#endif
+
 #if defined(BENCH_MT_FOR_EACH)
 static noinline void __init bench_mt_for_each(struct maple_tree *mt)
 {
@@ -3606,6 +3620,13 @@ static int __init maple_tree_seed(void)
 	mtree_destroy(&tree);
 	goto skip;
 #endif
+#if defined(BENCH_LOAD)
+#define BENCH
+	mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
+	bench_load(&tree);
+	mtree_destroy(&tree);
+	goto skip;
+#endif
 #if defined(BENCH_FORK)
 #define BENCH
 	mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
-- 
2.40.1