Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::3:7 as permitted sender) client-ip=2620:137:e000::3:7;
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 04/12] maple_tree: Add end of node tracking to the maple state
Date:   Wed,  1 Nov 2023 13:16:21 -0400
Message-Id: <20231101171629.3612299-5-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?3DDvnOln5hNmnwKU3+A+10lx9Acr9SkUCED+92Ae6lDnq0+2gVMzqUB6WM7l?=
 =?us-ascii?Q?YLU4UzgzdxiB2SRwIbQaGkwAbZX7EIBrItGzC26NjXW5tMt4J+pA39HaZBsg?=
 =?us-ascii?Q?yfgtaZ8zzW5PbtUVJJQsISN6So5ajcdnLkmy+VV5BOJeVz3szg0qpXdY+BrV?=
 =?us-ascii?Q?0pKUl15qRyAJaUN9NGJJdeczH7R7xZRNBxuRZ0LoPDmxZ3Tv7y68DNJyLAIM?=
 =?us-ascii?Q?s3CUO1o30UOTjTIk0G71DB+mKkqyMRHzZXaAVVumfVeHBaeaQqbVeD+OghJ7?=
 =?us-ascii?Q?mvesmPbCc4+dljjbew9ikIT271cEKFt3VKoyt8EVbe6c34f7T0C8j5j7x47Z?=
 =?us-ascii?Q?PnvUrraQXqTZl1Zi1IRs8l5Vlnx0JE9lvQynO+bbcWmBYrdgrB035wREWWRL?=
 =?us-ascii?Q?ScjLBBqEIrWqGIRrviuPcwSNF/rVF5KUnIwY5dTmNvRBPVKXJlf9RJRr9+hX?=
 =?us-ascii?Q?ynlDVzwoP6XFiAMxnmiPvWE8gP7zCAocvTqmByrRsMjyke9ssD8wpx8Ua1ML?=
 =?us-ascii?Q?R0BMg/npRb3nMKYAkatnPCq4zZoon51QW6S7uCWJ2T93Vm4FVnQjT/5OH3HJ?=
 =?us-ascii?Q?gUvDuekCXPWpiNcxyT2N5Z7wfryXTBN0MJcGZulATzlOz14KzDN2XZ3r1qo5?=
 =?us-ascii?Q?rBq/tPUdjj1g0uuoYlVuTmu1jYQMt1yCtvN1J5UPzdKCRiS5azNTb54cpDu9?=
 =?us-ascii?Q?CgcSm6mNqlf6Rw0O5/jBpQz5kfW1IZnjFVFlgw5s3s/02b13VRgc72lLcbzw?=
 =?us-ascii?Q?oFl8jF3F4f3UW02NzvP68/3W+R2jTBqCkbSm+DKjlMNqh7IEHF3WFErIe45X?=
 =?us-ascii?Q?8k3IuzaWCyO4EoEHzXoZgY6Jn+3yqSo1qhbhr5xyMNemdg9D8Qz0dZsgdVEN?=
 =?us-ascii?Q?LGQS1zDUCLjV8vczJ5QT/koSTNRC0K7lTXP7rvVizF2PF9TFxlmAyH8HxDjz?=
 =?us-ascii?Q?N2IkgbR/Hm3jaFCvizeyZFgrSoOASmrtWR90Vtl1u72vrcwHGgjauV5j3Zdo?=
 =?us-ascii?Q?eR1q4c+FLDCWJShj9HkmJ0W4zRLQHDva4y0THVg1IH8Jc18dJmFIjR/nn4Wh?=
 =?us-ascii?Q?7vfmhSlnFZxm0WVjD7xmy9C1gA1zIwnIJTzGhRjVeHRMFZVgMDFPZc5RhHnw?=
 =?us-ascii?Q?j5AkaEw6lp2mcqbM9OPCi4mWaBf4Jy97M9dWIpHvf+csb3fzHjlp+Ia7LNKv?=
 =?us-ascii?Q?JgAM4mRq4S9aYrc94A6/QKw1RaQTHsk4agVAfvLnYsDTWwSaFncv96NSW8eG?=
 =?us-ascii?Q?+be4uwA7yX0TpXF0Nqq9oM407Td21I3R/5EI1m26DTq3W2ijSO9XLSUvVY80?=
 =?us-ascii?Q?SHUnb280Bu7jvq7y0T2NtU2GLj10InJ0/9HnkYZxI7tOqAB+BvDEA3U5suj1?=
 =?us-ascii?Q?irBe5au+6f7BsQPNl0sN2J6kEUWrdW1McRRitWsF0fFEben+Mzt9+tEV9DOp?=
 =?us-ascii?Q?f04hOY0rAikLzpI0B6cLCbEDBjjjUOMW/2oJmM7a1LFSJN+dnL3q4isuziuU?=
 =?us-ascii?Q?Mu/UwinMNZ4YeUwVq8A/rOs2/BrwJgK6UNMJZ0KLysFLpbRIlHs6fGvooHV/?=
 =?us-ascii?Q?HM51gIqzfpwcZWiUFEE4Mk5Cn/FyO2Cl5cQpGhf4?=
X-MS-Exchange-AntiSpam-ExternalHop-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-ExternalHop-MessageData-0: Y09GF0puNYscXJoQiscny8gWrY/006qKoS+8lVl8veugZi2QqfbjZTE3NLkcEhgszGOwDFLc4QSxyUzLl86cESIWPWf472kdmWXFPGGIdrvggOiaEz4goK5cPTMlkmIkl1mtA992ltzxZwbWU3ccLQ8FHA/B1o+yrqc6fvrGpW41w9ZWYkpfhAsCAkit95NM17Z4MfW2xa6NS1tLqkgBdasS8Pw3H82ZqP9t2H6IDr2CYXnzDxEuyYtTdxrfDX64Mbls2EC1T3tmW689cIFZ8Yu5zBOS4crJF+i28kadkc2mQ3ehPSUuLu8iFj5zLKuGgy9lTtVf53dXJHKkrWQLPYkfOfq4jgqcl14i6z6B3NGblIeZD91M7LF45lN+d5gg37S6OsqucrZ/kJNMjrRNFCpP7+qLIpiV1aWeIjqx6pSJ9Xhn1dPBI3LO7mbv3NUVx5WvQW1ioKc2CehuhyDhkmPMXHB+x2t+i+yn7+3J9jG8fTqsr6FngP86vT1kXZtQ8xELzg32x+ha99cJSoguy4cpJRp7xZ2yfTULf8xsVTAvx2ybkvAR2qwtwX5qjmvqH0YgwHSAjV2cQ4vu1N+4N44i01AUkUd0hb6Jkzjht/evv8nS7uUVllB6SWrAeFQLmn1Jfs1blrro4oEGgrKTSZZCFegoRBwQMNCjyd6+IZTxqnAqZ1a76z/rYutd++GFz3uSVroNXCCSUDIGg4zSSAyD6oWBPjs6EdA8X3rmaZnt3DwsWRB+4MUxjAgheUaXRzEdzwBWnR0FStnWgy2guo985ir++JjCswnQFhIK7m2mpsDC+heEjmXWS2omtewYUXkm6QSZYJuoz6IANfgdPeJTXSlCX5VM9C0bNqAzsxHZbsTE6U3WrILLhavQaF/UiKhONhMd3JHkJUg7oOH1Bg==
X-OriginatorOrg: oracle.com
X-MS-Exchange-CrossTenant-Network-Message-Id: 71ed4287-7ff8-486f-ddfe-08dbdafe524f
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:44.1757
 (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: c2tsotqjw+udSt2YPS2WJbP+P1VNo3+C/XU2J1jnp5Q2Vmi/quRdgM8gJQ/mYFzpkVlZiJbFWHdD56AA/jOayg==
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-ORIG-GUID: -ueVWP9Ovf6FeZr49UWmsVYrr3cKZniZ
X-Proofpoint-GUID: -ueVWP9Ovf6FeZr49UWmsVYrr3cKZniZ
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,
        RCVD_IN_MSPIKE_H5,RCVD_IN_MSPIKE_WL,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
X-Greylist: Sender passed SPF test, not delayed by milter-greylist-4.6.4 (snail.vger.email [0.0.0.0]); Wed, 01 Nov 2023 10:17:35 -0700 (PDT)

Analysis of the mas_for_each() iteration showed that there is a
significant time spent finding the end of a node.  This time can be
greatly reduced if the end of the node is cached in the maple state.
Care must be taken to update & invalidate as necessary.

Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>
---
 include/linux/maple_tree.h       | 1 +
 lib/maple_tree.c                 | 7 +++++++
 tools/testing/radix-tree/maple.c | 1 +
 3 files changed, 9 insertions(+)

diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h
index 82a6bf5fa969..97a6adedb376 100644
--- a/include/linux/maple_tree.h
+++ b/include/linux/maple_tree.h
@@ -388,6 +388,7 @@ struct ma_state {
 	unsigned char depth;		/* depth of tree descent during write */
 	unsigned char offset;
 	unsigned char mas_flags;
+	unsigned char end;		/* The end of the node */
 };
 
 struct ma_wr_state {
diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index b6b2d7031cae..6634594c770a 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -2829,6 +2829,7 @@ static inline void *mtree_range_walk(struct ma_state *mas)
 			goto dead_node;
 	} while (!ma_is_leaf(type));
 
+	mas->end = end;
 	mas->offset = offset;
 	mas->index = min;
 	mas->last = max;
@@ -3495,6 +3496,7 @@ static noinline_for_kasan int mas_commit_b_node(struct ma_wr_state *wr_mas,
 	mas_replace_node(wr_mas->mas, old_enode);
 reuse_node:
 	mas_update_gap(wr_mas->mas);
+	wr_mas->mas->end = b_end;
 	return 1;
 }
 
@@ -3998,6 +4000,7 @@ static inline bool mas_wr_node_store(struct ma_wr_state *wr_mas,
 	}
 	trace_ma_write(__func__, mas, 0, wr_mas->entry);
 	mas_update_gap(mas);
+	mas->end = new_end;
 	return true;
 }
 
@@ -4178,6 +4181,7 @@ static inline bool mas_wr_append(struct ma_wr_state *wr_mas,
 	if (!wr_mas->content || !wr_mas->entry)
 		mas_update_gap(mas);
 
+	mas->end = new_end;
 	trace_ma_write(__func__, mas, new_end, wr_mas->entry);
 	return  true;
 }
@@ -4416,6 +4420,7 @@ static inline int mas_prev_node(struct ma_state *mas, unsigned long min)
 	if (unlikely(mte_dead_node(mas->node)))
 		return 1;
 
+	mas->end = mas->offset;
 	return 0;
 
 no_entry:
@@ -5062,6 +5067,7 @@ int mas_empty_area(struct ma_state *mas, unsigned long min,
 	if (mas->index < min)
 		mas->index = min;
 	mas->last = mas->index + size - 1;
+	mas->end = mas_data_end(mas);
 	return 0;
 }
 EXPORT_SYMBOL_GPL(mas_empty_area);
@@ -5122,6 +5128,7 @@ int mas_empty_area_rev(struct ma_state *mas, unsigned long min,
 		mas->last = max;
 
 	mas->index = mas->last - size + 1;
+	mas->end = mas_data_end(mas);
 	return 0;
 }
 EXPORT_SYMBOL_GPL(mas_empty_area_rev);
diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c
index e5da1cad70ba..cb4e4a7cc7f5 100644
--- a/tools/testing/radix-tree/maple.c
+++ b/tools/testing/radix-tree/maple.c
@@ -945,6 +945,7 @@ static inline bool mas_tree_walk(struct ma_state *mas, unsigned long *range_min,
 		goto retry;
 	}
 
+	mas->end = mas_data_end(mas);
 	return ret;
 
 not_found:
-- 
2.40.1