Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::3:3 as permitted sender) client-ip=2620:137:e000::3:3;
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 05/12] maple_tree: Use cached node end in mas_next()
Date:   Wed,  1 Nov 2023 13:16:22 -0400
Message-Id: <20231101171629.3612299-6-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?Eu/Kulx13QZCHna/ZocWqr+/wOIjyO7FKtpRu31+70h0SQkdkliRb9CXRXmk?=
 =?us-ascii?Q?Zdltzc28Bs7WYYpKVvSTwHF12QMOsPB2yGMDRPzSW6aBDiAz/6CFWzZcDYCN?=
 =?us-ascii?Q?7RJOOBjDJDLZpju5sjUbqpWmIoJsvkKgU45FTASaKxxKyoIWeBMh5EU301by?=
 =?us-ascii?Q?ydia5JXkUR1pOpraLGxa4wOLCVemtVyDVCQnAAyiyN1GWXqrCWtGAe4p/f4F?=
 =?us-ascii?Q?Wp52JpC0qcmoOWTbumvAT127oi2tsCQdv6OnNS4xnYmlv7MKqrTpLLUKVT8t?=
 =?us-ascii?Q?RR5QwxvbEr7VLVs5PwLRNd5BBgaxSCRgLmsY8oGCOxAJzl85i1YVpvaBHSmI?=
 =?us-ascii?Q?7syEzT31z53T97JUrOsrnimrF70flET6ToLs4BPkkcxUNi47XStHSFMPgkBN?=
 =?us-ascii?Q?FnFl1/QeN+8Wq24SACgbQButQLCr+8t9lX1usbrXMWhdi66Snrkfp2qHWiM4?=
 =?us-ascii?Q?3dQzpdbJdK18gYo1H2sUHsd7SSa1a0tqU0+GDrpat1I//or0JbXyTw/PHcUl?=
 =?us-ascii?Q?2cNkOwPD2sHKKVM7aHIC7Yc6RuQXt4KGMScS808bQW0RIv+mphUZZgaIyxm+?=
 =?us-ascii?Q?fQ2rxWuqAmlnc5BavKg+mn/nq5V3DFi9ybJNgwn7sboAE1ST6V/Es6X1V2ui?=
 =?us-ascii?Q?Nu6xGk8y50MoqawX3+HOH/ETofdksrRGLsTQ0441X3OqQOGqG7lmhZ7fU6YF?=
 =?us-ascii?Q?OffQQHPtBVMOI9FDya/L7lamuNlIYRcQdwwUTkPnclrOnGZn4cWF7ImQoexp?=
 =?us-ascii?Q?9bO4ggi59Hx2n2dPleFlVWrVKMt3bwU8734j+UU+6bKU8V+Q2XnSO5RAEgAR?=
 =?us-ascii?Q?/O71IyoEwK//glnOPrU8+cWKKNJhXFXFJ1dVsHPYCdfOQ9nGdlNW6ubWQsJu?=
 =?us-ascii?Q?WZ+TULUPFGn6FzTyW4p7ee2ZX29oFFnfLuOaWCZ24QGXdlT7m2YCv3fpDz7g?=
 =?us-ascii?Q?EGnkJ46Vjf9IppWxPt6V464YynSMGOlFWvKlr8jrZJ4pYPjym/TtElT0JKbG?=
 =?us-ascii?Q?SnCfkg5j95o3ogNttcGVz3TrNgJpDd7LcVwCfEM8IEDKRyUb+mTjODDQarFP?=
 =?us-ascii?Q?0kyMQ1GdR9BGT7daUg8Xg9Jfq5OQwn6dgtvdlX42DIB4Tfs+jH+7LbY0tKLB?=
 =?us-ascii?Q?Es40VJXit6DYiKsPjKM/69qIyWjdiK2Q1BmFjtb1pl6zyUTifN2JpfFEnErj?=
 =?us-ascii?Q?siSDHWsMiPsZiiN2+d4/FyDy9JyE2SnUbNAIyR11nEzrb2w+eGRzoyR6ve3Q?=
 =?us-ascii?Q?TyLJqHta7eoxR/MK1VP4aS8LtBwOUmM3zA+LE4ivJ2NNm7SEba1vIAgQXcrl?=
 =?us-ascii?Q?t43haWGQneKZe8jN8GJr2fPvM+HJEcHCRg0LsYsbA/kOyCnoFLMnftR9xPBb?=
 =?us-ascii?Q?Jdwh/9YpCXLKjyDc4rqCWTcTS1W2RdBrd9rOKtmwD9VZoOsvZ0kQmKjvBgI4?=
 =?us-ascii?Q?nPHD3a+H1k/pLFvS3ANK/PGJ3UDLhZvXkrg4b1mMqhaKnqlo6229LQrRho09?=
 =?us-ascii?Q?gMYBStEPSFTEjE8dfQkb1018ky1MOYJcayCSfhInJzUuYSpApWKe5y1MQn1z?=
 =?us-ascii?Q?HKvUVHQj633iCfb5o4uSK6rEfifR4G/21fw4sBM0GsN2xkUjQtJZZEqvm+rO?=
 =?us-ascii?Q?zQ=3D=3D?=
X-MS-Exchange-AntiSpam-ExternalHop-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-ExternalHop-MessageData-0: XB7lN1aTK4ie2UN5QUuEVeO4RuUtoJyyft4rkXkTOEWIQ+qL6bCRrNBxPkXuszNmhYDrTZi/sMvFHDTPAjt1BRtLwPdOZlh3B3Lsr6V9L6/oP//5oA60Q9Ex9G2DRb5fManz22xeMAvtXyk+BY0iTNvmFNMxbTu0DTPMQw5NTIWyrUvlNSNBKqF+wXRK1/FbZzbw06PCPaOgN+Q+XQUpuY9hyk1YhhYDZVNdQ+O+T5obdK8NWofg8spB+T8q9mBf0HXq9wXOoiSWvdXS/8LIADm3+A+kpq2WXj8gDvAzWkbN9HmLyUEvQXfIf+9UExyhFsAbGlhIAUDp7YP3f/LdU5R8DotMRuIJuE6ycUH76sn2XYi/iopqm1EDfx5vYlFFwtZd4iRMdvUaKT44X0yMrCIBZuc7bYYiODHW/9qAx9cnm2nHpG0BR4kSA7mSz5b+6iDItoBAMxW2TE5ekSs5uwJdN0gYmFF5D2H6H26L5gZbhekJYw5mnNhjl/jlP00mXlBZj6akN+v5C3gkrUi5MgcoZ55lJMUTVfff4MqImLDTNR23LWx+e01ZzrvvBdBuf9tqsXXEI6+rdEdqtffHr/l81+gsfbrjpRP4PjiOAzMBHEtaa4A7UbMazRjQ4AnwPnL4hc9FDqm/aUfoFYsUN3IpWv2Bp/RmqEhkDaegu3FHnI7ajPG7cua5ghc4fXi0tPtZvh09DqVH2tHSeK96oBrBIYt5mbx8P1bMrMOkqURH/hj4TadIo+xqpoC4972GJPm/Dl7brLgPY+9VZaf4sq2kAsjtXacRLHaB1m02C58UFITMK8NCKmOi75bZA+JgW+WLGl6nhJeIhbXX4+UKkWjlZC5VENn3ohfKoc6wK3iWC8eAIp5ZN8ZD1/7GL2r75O2SdbJkRBPmaXMK5f7e2A==
X-OriginatorOrg: oracle.com
X-MS-Exchange-CrossTenant-Network-Message-Id: c94c6aab-21f4-4c57-4930-08dbdafe533e
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:45.6887
 (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: bSKPAcg4SdN3Lz+AFJB9B+KwjsTN7BC8hRzUdA9u8hI9Aaf7js09m4uWg8mxSjOdAWujRwuP4h9Hgvp2t44cjQ==
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 spamscore=0 adultscore=0 mlxscore=0
 suspectscore=0 mlxlogscore=999 bulkscore=0 phishscore=0 malwarescore=0
 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2310240000
 definitions=main-2311010134
X-Proofpoint-GUID: LYREdPvwMBxsH7qpOZXLM-2NRLbw3hzV
X-Proofpoint-ORIG-GUID: LYREdPvwMBxsH7qpOZXLM-2NRLbw3hzV
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 lipwig.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 (lipwig.vger.email [0.0.0.0]); Wed, 01 Nov 2023 10:17:36 -0700 (PDT)

When looking for the next entry, don't recalculate the node end as it is
now tracked in the maple state.

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

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 6634594c770a..6c0ed71844e6 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -4527,6 +4527,7 @@ static inline int mas_next_node(struct ma_state *mas, struct maple_node *node,
 	unsigned long min;
 	unsigned long *pivots;
 	struct maple_enode *enode;
+	struct maple_node *tmp;
 	int level = 0;
 	unsigned char node_end;
 	enum maple_type mt;
@@ -4579,6 +4580,10 @@ static inline int mas_next_node(struct ma_state *mas, struct maple_node *node,
 		pivots = ma_pivots(node, mt);
 
 	mas->max = mas_safe_pivot(mas, pivots, mas->offset, mt);
+	tmp = mte_to_node(enode);
+	mt = mte_node_type(enode);
+	pivots = ma_pivots(tmp, mt);
+	mas->end = ma_data_end(tmp, mt, pivots, mas->max);
 	if (unlikely(ma_dead_node(node)))
 		return 1;
 
@@ -4613,7 +4618,6 @@ static void *mas_next_slot(struct ma_state *mas, unsigned long max, bool empty,
 	unsigned long pivot;
 	enum maple_type type;
 	struct maple_node *node;
-	unsigned char data_end;
 	unsigned long save_point = mas->last;
 	void *entry;
 
@@ -4621,12 +4625,11 @@ static void *mas_next_slot(struct ma_state *mas, unsigned long max, bool empty,
 	node = mas_mn(mas);
 	type = mte_node_type(mas->node);
 	pivots = ma_pivots(node, type);
-	data_end = ma_data_end(node, type, pivots, mas->max);
 	if (unlikely(mas_rewalk_if_dead(mas, node, save_point)))
 		goto retry;
 
 	if (mas->max >= max) {
-		if (likely(mas->offset < data_end))
+		if (likely(mas->offset < mas->end))
 			pivot = pivots[mas->offset];
 		else
 			goto overflow;
@@ -4638,11 +4641,11 @@ static void *mas_next_slot(struct ma_state *mas, unsigned long max, bool empty,
 			goto overflow;
 	}
 
-	if (likely(mas->offset < data_end)) {
+	if (likely(mas->offset < mas->end)) {
 		mas->index = pivots[mas->offset] + 1;
 again:
 		mas->offset++;
-		if (likely(mas->offset < data_end))
+		if (likely(mas->offset < mas->end))
 			mas->last = pivots[mas->offset];
 		else
 			mas->last = mas->max;
@@ -4679,7 +4682,6 @@ static void *mas_next_slot(struct ma_state *mas, unsigned long max, bool empty,
 			goto overflow;
 
 		mas->index = mas->last + 1;
-		/* Node cannot end on NULL, so it's safe to short-cut here */
 		goto again;
 	}
 
-- 
2.40.1